(Analysis by Chris Zhang)

For the first two subtasks, we can just simulate. $NK$ minutes will suffice because the sequence of positions of an individual cow will start repeating within that time.

Now, onto the full solution. After the first $K$ swaps, we compute where each cow ends up. If a cow started at the $i$-th position, let its new position be $p_i$. Let’s also track the set $s_i$ of all positions that cow $i$ reached during the $K$ swaps. This does not take too much memory because the sum of the sizes of all sets $s_i$ is bounded by $2K+N$ (every swap, at most two cows move, thus adding at most two elements to the sets).

Let’s build a directed graph on the positions that shows how the cows move every $K$ swaps. We have $N$ directed edges from all $i$ to $p_i$ $(1 \le i \le N)$. This graph is a bunch of cycles because after $K$ swaps, there is exactly one cow in each position, so the outdegree and indegree of each node is one. Therefore, the graph is a bunch of disjoint cycles (as with Swapity Swapity Swap).

We claim that the answers for all cows in the same cycle are the same. Because everything repeats every $K$ swaps, if two cows have ever been in the same position after a multiple of $K$ swaps, they would visit the same positions eventually. After $K$ swaps, cow $i$ goes to position $p_i$, so the answers for cow $i$ and cow $p_i$ are the same. This logic extends to every cow in the cycle (the answer for cow $p_i$ is equal to cow $p_{p_i}$ and so on).

So, what exactly is the answer for some cycle? It’s the size of the union of all the sets $s_i$ for each cow $i$ in the cycle. In other words, the answer is the number of unique positions in all the sets in the cycle. The complexity of this solution is $\mathcal{O}(N+K)$.

Chris’ code:

#include <bits/stdc++.h>
using namespace std;

int N,K;
int A[200001],B[200001]; //input
int P[100001]; //as described in analysis
vector<int>S[100001]; //as described in analysis
int from[100001]; //from[i] = where the cow in position i originated from
int cnt[100001]; //array to keep track of uniquePos
int uniquePos; //# of unique reachable positions

for (int x:S[node]){
if (cnt[x]==0)
uniquePos++;
cnt[x]++;
}
}

//remove S_node
void remove(int node){
for (int x:S[node]){
if (cnt[x]==1)
uniquePos--;
cnt[x]--;
}
}

bool vis[100001];
queue<int>q; //stores all nodes in current cycle

void dfs(int node){
vis[node]=true;
q.push(node);
if (!vis[P[node]])
dfs(P[node]);
}

int main(){
cin>>N>>K;
for (int i=0;i<K;i++)
cin>>A[i]>>B[i];
//initialize from and S
for (int i=1;i<=N;i++){
from[i]=i;
S[i].push_back(i);
}
//simulate the first K swaps, keeping track of where each position can reach
for (int i=0;i<K;i++){
S[from[A[i]]].push_back(B[i]);
S[from[B[i]]].push_back(A[i]);
swap(from[A[i]],from[B[i]]);
}
//compute array P after first K swaps
for (int i=1;i<=N;i++)
P[from[i]]=i;
int ans[100001];
//run a DFS on each cycle
for (int i=1;i<=N;i++)
if (!vis[i]){
dfs(i);
//assign the answer for all nodes in the cycle, which we've stored in this queue
while (!q.empty()){
remove(q.front());
ans[q.front()]=tempAns;
q.pop();
}
}
for (int i=1;i<=N;i++)
cout<<ans[i]<<endl;
return 0;
}


Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;

public class DanceMoovesSilver {

public static void main(String[] args) throws IOException {
int n = Integer.parseInt(tokenizer.nextToken());
int k = Integer.parseInt(tokenizer.nextToken());
int[] cows = new int[n + 1];
List<Integer>[] viewed = new List[n + 1];
for (int j = 1; j <= n; j++) {
cows[j] = j;
viewed[j] = new ArrayList<>();
}
for (long t = 1; t <= k; t++) {
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
int c = cows[a];
int d = cows[b];
cows[a] = d;
cows[b] = c;
}
int[] answer = new int[n + 1];
for (int r = 1; r <= n; r++) {
if (cows[r] != 0) {
List<Integer> cycle = new ArrayList<>();
int j = r;
while (cows[j] != 0) {
j = cows[j];
cows[cycle.get(cycle.size() - 1)] = 0;
}
Set<Integer> viewedHere = new HashSet<>();
for (int cow : cycle) {
}
for (int cow : cycle) {