#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 3010;
int E[M], n;
vector<int> R[M];
ll k;
int ans[M], ck[M];
int in_cycle[M];
vector<vector<int>> cycle;
void find_cycle(int x){
vector<int> V;
while(!ck[x]) {
ck[x] = 1;
V.push_back(x);
x = E[x];
}
int p = find(V.begin(),V.end(),x) - V.begin();
if(p>=V.size()) return;
cycle.push_back({});
for(int i = p;i<V.size();i++) {
in_cycle[V[i]]=1;
cycle.back().push_back(V[i]);
}
}
void dfs(int x, int dist,int dep, vector<int> L){ //
ck[x] = 1;
L.push_back(x);
//fi[v] 가 나에게 온다면?
ans[L[(L.size() - (dist%L.size()))%L.size()]]++;
for(auto i : R[x]) {
dfs(i,dist,dep+1,L);
}
L.pop_back();
}
void dfs2(int x,int s,int dep,int dist,int ver){
ans[cycle[ver][(s-dep+dist)%cycle[ver].size()]]++;
for(auto i : R[x]) if(!in_cycle[i]) {
dfs2(i,s,dep+1,dist,ver);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for(int i = 1;i<=n;i++){
cin >> E[i];
}
vector<int> first_cycle;
int p = 1;
while(!ck[p]){
ck[p] = 1;
first_cycle.push_back(p);
p = E[p];
}
int p1 = find(first_cycle.begin(),first_cycle.end(),p) - first_cycle.begin();
int w = first_cycle[(k-p1)%(first_cycle.size()-p1)+p1];
ans[w] += ((ll)n-first_cycle.size())*n;
for(int v = 0;v<first_cycle.size();v++) {
// first[v]에서 가는 간선은 이제 없다.
for(int i = 1;i<=n;i++) ck[i] = 0;
for(int i = 1;i<=n;i++) in_cycle[i] = 0;
for(int i = 1;i<=n;i++) R[i].clear();
cycle.clear();
for(int i = 1;i<=n;i++) if(i^first_cycle[v]){
R[E[i]].push_back(i);
}
vector<int> L;
dfs(first_cycle[v],k-v,0,L);
// 내 트리로 가는게 아닌 경우
for(int i = 1;i<=n;i++) if(!ck[i])
find_cycle(i);
int dist = k-v-1;
for(int i = 0;i<cycle.size();i++)
for(int j = 0;j<cycle[i].size();j++)
dfs2(cycle[i][j],j,0,dist,i);
}
for(int i = 1;i<=n;i++) cout << ans[i] << '\n';
}
Compilation message
space_pirate.cpp: In function 'void find_cycle(int)':
space_pirate.cpp:19:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | if(p>=V.size()) return;
| ~^~~~~~~~~~
space_pirate.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = p;i<V.size();i++) {
| ~^~~~~~~~~
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int v = 0;v<first_cycle.size();v++) {
| ~^~~~~~~~~~~~~~~~~~~
space_pirate.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0;i<cycle.size();i++)
| ~^~~~~~~~~~~~~
space_pirate.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int j = 0;j<cycle[i].size();j++)
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
