oj.uz

Submission #52282

# Submission time Handle Problem Language Result Execution time Memory
52282 2018-06-25T07:45:47 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;

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 f(int a,int b)
{
	if(a == b) return a;
	
	if(a == 1){
		if(K[b][1]){
			ll r = k % (K[b][1] + 1);
			if(r == 0) return a;
			else if(r == 1) return b;
			else return run(b, r-1);
		}
		else return run(b, k-1);
	}
	
	if(K[b][a]){
		ll r = (k - K[1][a]) % (K[b][a] + 1);
		if(r == 0) return a;
		else if(r == 1) return b;
		else return run(b, r-1);
	}
	else return run(b, k-1-K[1][a]);
}	

int main()
{
	scanf("%d%d",&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;
	
	for(i=1;i<=n;i++) if(i == 1 || K[1][i]){
		for(j=1;j<=n;j++){
			ans[f(i,j)] ++;
		}
		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:45:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
  scanf("%d%d",&n,&k);
                  ~~^
space_pirate.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
space_pirate.cpp:54: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 -