oj.uz

Submission #52293

# Submission time Handle Problem Language Result Execution time Memory
52293 2018-06-25T08:11:25 Z 김세빈(#1347) Space Pirate (JOI14_space_pirate) C++11
47 / 100
 1628 ms 71236 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,x1;
	
	for(i=1;i<=n;i++){
		scanf("%d",P+i);
	}
	
	int fff = 0;
	
	for(i=1;i<=n;i++){
		for(j=i,t=0;;j=P[j],t++){
			if(K[j][i]) break;
			K[j][i] = t;
			B[i][t] = j;
			fff ++;
		}
		R[i] = t-K[j][i];
		F[i] = K[j][i];
	}
	
	int cnt = 0;
	
	ans[1] ++;
	for(i=2;i<=n;i++){
		if(K[1][i]){
			ll r = k % (K[1][i] + 1);
			if(r == 0) ans[1] ++;
			else ans[run(i, r-1)] ++;
		}
		else ans[run(i, k-1)] ++;
	}
	
	for(i=2;i<=n;i++) if(K[i][1]){
		x1 = K[i][1];
		for(j=1;j<=n;j++){
			if(i == j) ans[i] ++;
			else{
				if(K[i][j]){
					r = (k - x1) % (K[i][j] + 1);
					if(r == 0) ans[i] ++;
					else ans[run(j, r-1)] ++;
				}
				else ans[run(j, k-1-x1)] ++;
			}
		}
		cnt ++;
	}
	
	ans[run(1,k)] += n * (n - cnt - 1);
	
	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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 3 ms 1176 KB Output is correct
4 Correct 4 ms 1304 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 4 ms 1440 KB Output is correct
9 Correct 3 ms 1440 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct
11 Correct 4 ms 1456 KB Output is correct
12 Correct 4 ms 1456 KB Output is correct
13 Correct 4 ms 1456 KB Output is correct
14 Correct 3 ms 1456 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 3 ms 1176 KB Output is correct
4 Correct 4 ms 1304 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 4 ms 1440 KB Output is correct
9 Correct 3 ms 1440 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct
11 Correct 4 ms 1456 KB Output is correct
12 Correct 4 ms 1456 KB Output is correct
13 Correct 4 ms 1456 KB Output is correct
14 Correct 3 ms 1456 KB Output is correct
15 Correct 66 ms 38112 KB Output is correct
16 Correct 34 ms 38112 KB Output is correct
17 Correct 62 ms 38112 KB Output is correct
18 Correct 1593 ms 71236 KB Output is correct
19 Correct 861 ms 71236 KB Output is correct
20 Correct 812 ms 71236 KB Output is correct
21 Correct 1491 ms 71236 KB Output is correct
22 Correct 688 ms 71236 KB Output is correct
23 Correct 962 ms 71236 KB Output is correct
24 Correct 389 ms 71236 KB Output is correct
25 Correct 44 ms 71236 KB Output is correct
26 Correct 1628 ms 71236 KB Output is correct
27 Correct 567 ms 71236 KB Output is correct
28 Correct 702 ms 71236 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 3 ms 1176 KB Output is correct
4 Correct 4 ms 1304 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 4 ms 1440 KB Output is correct
9 Correct 3 ms 1440 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct
11 Correct 4 ms 1456 KB Output is correct
12 Correct 4 ms 1456 KB Output is correct
13 Correct 4 ms 1456 KB Output is correct
14 Correct 3 ms 1456 KB Output is correct
15 Correct 66 ms 38112 KB Output is correct
16 Correct 34 ms 38112 KB Output is correct
17 Correct 62 ms 38112 KB Output is correct
18 Correct 1593 ms 71236 KB Output is correct
19 Correct 861 ms 71236 KB Output is correct
20 Correct 812 ms 71236 KB Output is correct
21 Correct 1491 ms 71236 KB Output is correct
22 Correct 688 ms 71236 KB Output is correct
23 Correct 962 ms 71236 KB Output is correct
24 Correct 389 ms 71236 KB Output is correct
25 Correct 44 ms 71236 KB Output is correct
26 Correct 1628 ms 71236 KB Output is correct
27 Correct 567 ms 71236 KB Output is correct
28 Correct 702 ms 71236 KB Output is correct
29 Incorrect 3 ms 71236 KB Output isn't correct
30 Halted 0 ms 0 KB -