competitive-programming/Codeforces/1327/d.cpp at master · eyangch/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define endl '\n'
#define eat cin
#define moo cout
#define int long long

using namespace std;

int T, N, p[200000], c[200000];
bool vis[200000];

int32_t main(){
    eat.tie(0) -> sync_with_stdio(0);
    eat >> T;
    while(T--){
        eat >> N;
        for(int i = 0; i < N; i++) eat >> p[i];
        for(int i = 0; i < N; i++) eat >> c[i];
        fill(vis, vis+N, 0);
        int ans = 1e9;
        for(int i = 0; i < N; i++){
            vector<int> cy;
            int ptr = i;
            while(!vis[ptr]){
                vis[ptr] = true;
                cy.push_back(c[ptr]);
                ptr = p[ptr] - 1;
            }
            if(cy.empty()) continue;
            for(int j = 1; j * j <= (int)cy.size(); j++){
                if((int)cy.size() % j == 0){
                    for(int k = 0; k < j; k++){
                        int match = cy[k];
                        bool good = true;
                        for(int l = j + k; l < (int)cy.size(); l += j){
                            if(cy[l] != match){
                                good = false;
                                break;
                            }
                        }
                        if(good){
                            ans = min(ans, j);
                            break;
                        }
                    }
                    for(int k = 0; k < (int)cy.size() / j; k++){
                        int match = cy[k];
                        bool good = true;
                        for(int l = (int)cy.size() / j + k; l < (int)cy.size(); l += (int)cy.size() / j){
                            if(cy[l] != match){
                                good = false;
                                break;
                            }
                        }
                        if(good){
                            ans = min(ans, (int)cy.size() / j);
                            break;
                        }
                    }
                }
            }
        }
        moo << ans << endl;
    }
}