oj.uz

Submission #52286

# Submission time Handle Problem Language Result Execution time Memory
52286 2018-06-25T07:57:55 Z 김세빈(#1347) Space Pirate (JOI14_space_pirate) C++11
0 / 100
 3 ms 1144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int K[3030][3030], B[3030][3030];
int R[3030], F[3030], P[101010];
int ans[101010];
int n;
ll k,r;

int run(int p,ll d)
{
	if(d <= F[p]) return B[p][d];
	if(d == 0) return p;
	return B[p][(d - F[p]) % R[p] + F[p]];
}

int main()
{
	scanf("%d%lld",&n,&k);
	
	if(n > 3000){
		return 0;
	}
	
	int i,j,t;
	
	for(i=1;i<=n;i++){
		scanf("%d",P+i);
	}
	
	for(i=1;i<=n;i++){
		for(j=i,t=0;;j=P[j],t++){
			if(K[i][j]) break;
			K[i][j] = t;
			B[i][t] = j;
		}
		R[i] = t-K[i][j];
		F[i] = K[i][j];
	}
	
	ll cnt = 0;
	
	ans[1] ++;
	for(i=2;i<=n;i++){
		if(K[i][1]){
			ll r = k % (K[i][1] + 1);
			if(r == 0) ans[1] ++;
			else if(r == 1) ans[i] ++;
			else ans[run(i, r-1)] ++;
		}
		else ans[run(i, k-1)] ++;
	}
	
	for(i=2;i<=n;i++) if(K[1][i]){
		for(j=1;j<=n;j++){
			if(i == j) ans[i] ++;
			else{
				if(K[j][i]){
					r = (k - K[1][i]) % (K[j][i] + 1);
					if(r == 0) ans[i] ++;
					else if(r == 1) ans[j] ++;
					else ans[run(j, r-1)] ++;
				}
				else ans[run(j, k-1-K[1][i])] ++;
			}
		}
		cnt ++;
	}
	
	ans[run(1,k)] += n * (n - cnt);
	
	for(i=1;i<=n;i++) printf("%d\n",ans[i]);
	
	return 0;
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~
space_pirate.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",P+i);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -