Submission #649183

#	Time	Username	Problem	Language	Result	Execution time	Memory
649183		gggkik	Space Pirate (JOI14_space_pirate)	C++14	47 / 100	468 ms	820 KiB

space_pirate

#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;
ll ans[M];
int ck[M], 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,ll 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,ll 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);
		ll 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 (stderr)

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++)
      |                  ~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20