Submission #110817

#	Time	Username	Problem	Language	Result	Execution time	Memory
110817		autumn_eel	Space Pirate (JOI14_space_pirate)	C++14	47 / 100	1529 ms	37156 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[3100];

int a[3100];
int ans[3100];

P vis[3100];
int cycle[3100];

P d[3100];
int d1[3100];
int dist[3100];

int id[3100][3100];

int cnt=0;

void dfs(int v,int k){
	vis[v]=P(cnt,k);
	if(vis[a[v]].first!=-1){
		if(vis[a[v]].second!=k||cycle[a[v]])return;
		cycle[a[v]]=cnt+1-vis[a[v]].first;
	}
	cnt++;
	dfs(a[v],k);
}

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){
		vis[i]=P(-1,-1);
	}
	int c1=0;
	rep(i,n){
		if(vis[i].first==-1){
			dfs(i,c1++);
		}
	}
	queue<int>que;
	rep(i,n)d[i]=P(-1,i);
	rep(i,n){
		if(cycle[i]){
			d[i]=P(0,i);
			que.push(i);
		}
	}
	while(!que.empty()){
		int p=que.front();que.pop();
		for(int u:E[p]){
			if(d[u].first==-1){
				d[u]=P(d[p].first+1,d[p].second);
				que.push(u);
			}
		}
	}
	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){
			if(K<d[0].first)ans[id[0][K]]+=n;
			else{
				ans[id[d[0].second][(K-d[0].first)%cycle[d[0].second]]]+=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].first)ans[id[j][b-1]]++;
				else{
					ans[id[d[j].second][(b-d[j].first-1)%cycle[d[j].second]]]++;
				}
			}
		}
	}
	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: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20