# CodeForces 1327D - Infinite Path

2020-03-24 15:30 CST

## Solution

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

int n = 0, cnt = 0, len = 0;
int p[200005] = {};
int c[200005] = {};
int idx[200005] = {};
int off[200005] = {};
int nex[200005] = {};
bool vis[200005] = {};
vector<int> g[200005];

void dfs(int pos) {
if (vis[pos]) return;
vis[pos] = true;
idx[pos] = cnt;
off[pos] = len++;
g[cnt].emplace_back(pos);
dfs(p[pos]);
}

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
cnt = 0;
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &p[i]);
p[i] = p[i] - 1;
}
for (int i = 0; i < n; ++i) {
scanf("%d", &c[i]);
}
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
len = 0;
g[cnt].clear();
dfs(i);
++cnt;
}
}
int ans = n;
for (int i = 0; i < cnt; ++i) {
len = g[i].size();
for (int j = 1; j <= len; ++j) {
if (len % j == 0) {
for (int k = 0; k < len; ++k) {
vis[g[i][k]] = false;
nex[g[i][k]] = g[i][(k + j) % len];
}
for (int k = 0; k < len; ++k) {
if (!vis[g[i][k]]) {
bool flag = true;
int pos = nex[g[i][k]];
while (pos != g[i][k]) {
vis[pos] = true;
if (c[pos] != c[g[i][k]]) {
flag = false;
break;
}
pos = nex[pos];
}
if (flag) {
ans = min(ans, j);
break;
}
}
}
}
}
}
printf("%d\n", ans);
}
return 0;
}

<EOF>