For the first subtask, we can just simulate. At most $NK$ minutes will suffice because the sequence of positions of an individual cow will start repeating within that time. For the second subtask, see the silver analysis.
For full credit, let's again construct $s_i$ and $p_i$ as described in the Silver analysis, and consider the contribution of each disjoint cycle independently.
Let $D={\lfloor}{M/K}{\rfloor}$ and $R$ be the remainder when $M$ is divided by $K$. There will first occur $D$ full iterations of $K$ swaps, followed by $R$ extra swaps. For simplicity, let’s ignore $R$ for now. To solve for the answer of cow $i$, which is in some cycle of length $L$: if $D$ is at least $L$, the answer is the size of the union of all sets $s_i$ in this cycle (as in the silver analysis). But if $D$ is less than $L$, it will be the size of the union of the $D$ sets $s_i, s_{p_i}, s_{p^2_i}, \cdots, s_{p^{D-1}_i}$. To compute the answers for all cows in a cycle, we maintain a “sliding window” of length $D$ and keep track of the number of unique positions in an array. Specifically, to get the window for $p_i$ from the window for $i$, we remove the set $s_i$ and add the set $s_{p^D_i}$.
Now, returning back to $R$. We can actually iterate across each set $s_i$ to account for the $R$ extra swaps. This is fast enough because we only iterate across each set at most once, the sum of the sizes of all sets $s_i$ is bounded by $2K+N$. To implement this, let the sets $s_i$ store pairs which include both the positions and the times at which the positions are reached.
The complexity of this solution is $\mathcal{O}(N+K)$.
Chris’ code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,K;
ll M;
int A[200001],B[200001]; //input
int P[100001]; //as described in analysis
int from[100001]; //from[i] = where the cow in position i originated from
vector<pair<int,int>>S[100001]; //as described in analysis, stores {pos, time}
int cnt[100001]; //array to keep track of uniquePos
int uniquePos; //# of unique reachable positions
//adds in all reachable positions from S_node where time<=bar
void add(int node, int bar){
for (auto x:S[node]){
if (x.second>bar) return;
if (cnt[x.first]==0)
uniquePos++;
cnt[x.first]++;
}
}
//removes all reachable positions from S_node where time<=bar
void remove(int node, int bar){
for (auto x:S[node]){
if (x.second>bar) return;
if (cnt[x.first]==1)
uniquePos--;
cnt[x.first]--;
}
}
vector<int>nodes; //stores nodes currently in cycle
bool vis[100001];
void dfs(int node){
vis[node]=true;
nodes.push_back(node);
if (!vis[P[node]])
dfs(P[node]);
}
int main(){
cin>>N>>K>>M;
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,0});
}
//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],i+1});
S[from[B[i]]].push_back({A[i],i+1});
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);
ll D=M/K; //as described in the analysis
int R=M%K; //as described in the analysis
//"special case" if the whole cycle is included
if (D>=(int)nodes.size()){
D=nodes.size();
R=0;
}
int j=D-1;
//initialize our sliding window [0,j]
for (int k=0;k<=j;k++)
add(nodes[k],K);
//we slide our window [i,j], adding and removing as we go
for (int i=0;i<nodes.size();i++){
int newJ=(j+1)%(int)nodes.size();
//account for the extra R swaps
add(nodes[newJ],R);
//store answer for current sliding window
ans[nodes[i]]=uniquePos;
//undo the extra R swaps
remove(nodes[newJ],R);
//undo the left endpoint of sliding window
remove(nodes[i],K);
//add new right endpoint of sliding window
add(nodes[newJ],K);
j=newJ;
}
//reset everything from this cycle
for (int k=0;k<=D-1;k++)
remove(nodes[k],K);
nodes.clear();
}
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.io.InputStreamReader;
import java.util.*;
public class DanceMooves {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
long k = Integer.parseInt(tokenizer.nextToken());
long m = Long.parseLong(tokenizer.nextToken());
int[] cows = new int[n + 1];
List<View>[] views = new List[n + 1];
for (int j = 1; j <= n; j++) {
cows[j] = j;
views[j] = new ArrayList<>();
views[j].add(new View(j, 0));
}
for (long t = 1; t <= k; t++) {
tokenizer = new StringTokenizer(in.readLine());
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;
views[cows[a]].add(new View(a, t));
views[cows[b]].add(new View(b, t));
}
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) {
cycle.add(j);
j = cows[j];
cows[cycle.get(cycle.size() - 1)] = 0;
}
Map<Integer, List<Interval>> intervalMap = new HashMap<>();
for (j = 0; j < cycle.size(); j++) {
for (View view : views[cycle.get(j)]) {
if (m >= view.time) {
int covered = (int) Math.min((long) cycle.size(), ((m - view.time) / k) + 1L);
if (!intervalMap.containsKey(view.position)) {
intervalMap.put(view.position, new ArrayList<>());
}
intervalMap.get(view.position).add(new Interval(j, Math.min(cycle.size(), j + covered)));
if (j + covered > cycle.size()) {
intervalMap.get(view.position).add(new Interval(0, (j + covered) % cycle.size()));
}
}
}
}
int[] amts = new int[cycle.size() + 1];
for (List<Interval> intervals : intervalMap.values()) {
intervals.sort(Comparator.comparingInt(interval -> interval.from));
int prev = 0;
for (Interval interval : intervals) {
amts[Math.max(prev, interval.from)]++;
prev = Math.max(prev, interval.until);
amts[prev]--;
}
}
for (j = 0; j < cycle.size(); j++) {
answer[cycle.get(j)] = amts[j];
amts[j + 1] += amts[j];
}
}
}
StringBuilder out = new StringBuilder();
for (int j = 1; j <= n; j++) {
out.append(answer[j]).append('\n');
}
System.out.print(out);
}
static class View {
final int position;
final long time;
View(int position, long time) {
this.position = position;
this.time = time;
}
}
static class Interval {
final int from;
final int until;
Interval(int from, int until) {
this.from = from;
this.until = until;
}
}
}