Submission #110800

#	Time	Username	Problem	Language	Result	Execution time	Memory
110800		autumn_eel	Space Pirate (JOI14_space_pirate)	C++14	0 / 100	6 ms	1664 KiB

space_pirate

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

vector<int>E[4000];

int a[4000];
int ans[4000];

int vis[4000];
int cycle[4000];

int d[4000];
int d1[4000];
int dist[4000];

int id[4000][4000];

int cnt=0;

void dfs(int v){
	vis[v]=cnt;
	if(vis[a[v]]!=-1){
		if(cycle[a[v]])return;
		cycle[a[v]]=cnt+1-vis[a[v]];
	}
	cnt++;
	dfs(a[v]);
}

void bfs(queue<int>&que,int d[]){
	while(!que.empty()){
		int p=que.front();que.pop();
		for(int u:E[p]){
			if(d[u]==-1){
				d[u]=d[p]+1;
				que.push(u);
			}
		}
	}
}

int main(){
	int n;ll K;cin>>n>>K;
	if(n>3000)abort();
	rep(i,n){
		scanf("%d",&a[i]);a[i]--;
		E[a[i]].push_back(i);
	}
	rep(i,n){
		int x=i;
		rep(j,n+1){
			id[i][j]=x;
			x=a[x];
		}
	}
	memset(vis,-1,sizeof(vis));
	rep(i,n){
		if(vis[i]==-1){
			dfs(i);
		}
	}
	queue<int>que;
	memset(d,-1,sizeof(d));
	rep(i,n){
		if(cycle[i]){
			d[i]=0;
			que.push(i);
		}
	}
	bfs(que,d);
	memset(d1,-1,sizeof(d1));
	int x=0;
	d1[0]=0;
	while(1){
		if(d1[a[x]]!=-1)break;
		d1[a[x]]=d1[x]+1;
		x=a[x];
	}
	rep(i,n){
		if(d1[i]>=K||d1[i]==-1){
			ans[id[0][K%cycle[0]]]+=n;
			continue;
		}
		memset(dist,-1,sizeof(dist));
		dist[i]=0;
		que.push(i);
		bfs(que,dist);
		ll b=K-d1[i];
		rep(j,n){
			if(dist[j]!=-1){
				int cy=dist[j]+1;
				if(b%cy==0){
					ans[i]++;
				}
				else ans[id[j][b%cy-1]]++;
			}
			else{
				if(b<d[j])ans[id[j][b-1]]++;
				else{
					ans[id[j][(b-d[j])%cycle[j]]]++;
				}
			}
		}
	}
	rep(i,n){
		printf("%d\n",ans[i]);
	}
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);a[i]--;
   ~~~~~^~~~~~~~~~~~

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