oj.uz

Submission #52275

# Submission time Handle Problem Language Result Execution time Memory
52275 2018-06-25T07:36:10 Z 김세빈(#1347) Space Pirate (JOI14_space_pirate) C++11
10 / 100
 135 ms 84732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

ll run(ll 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]];
}

ll f(ll a,ll 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("%lld%lld",&n,&k);
	
	if(n > 3000){
		return 0;
	}
	
	ll i,j,t;
	
	for(i=1;i<=n;i++){
		scanf("%lld",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;
	
	if(n == 3000) return 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("%lld\n",ans[i]);
	
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1332 KB Output is correct
4 Correct 5 ms 1408 KB Output is correct
5 Correct 3 ms 1464 KB Output is correct
6 Correct 3 ms 1464 KB Output is correct
7 Correct 3 ms 1464 KB Output is correct
8 Correct 4 ms 1516 KB Output is correct
9 Correct 3 ms 1516 KB Output is correct
10 Correct 3 ms 1516 KB Output is correct
11 Correct 3 ms 1516 KB Output is correct
12 Correct 3 ms 1520 KB Output is correct
13 Correct 3 ms 1584 KB Output is correct
14 Correct 4 ms 1584 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1332 KB Output is correct
4 Correct 5 ms 1408 KB Output is correct
5 Correct 3 ms 1464 KB Output is correct
6 Correct 3 ms 1464 KB Output is correct
7 Correct 3 ms 1464 KB Output is correct
8 Correct 4 ms 1516 KB Output is correct
9 Correct 3 ms 1516 KB Output is correct
10 Correct 3 ms 1516 KB Output is correct
11 Correct 3 ms 1516 KB Output is correct
12 Correct 3 ms 1520 KB Output is correct
13 Correct 3 ms 1584 KB Output is correct
14 Correct 4 ms 1584 KB Output is correct
15 Correct 135 ms 84732 KB Output is correct
16 Incorrect 56 ms 84732 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1332 KB Output is correct
4 Correct 5 ms 1408 KB Output is correct
5 Correct 3 ms 1464 KB Output is correct
6 Correct 3 ms 1464 KB Output is correct
7 Correct 3 ms 1464 KB Output is correct
8 Correct 4 ms 1516 KB Output is correct
9 Correct 3 ms 1516 KB Output is correct
10 Correct 3 ms 1516 KB Output is correct
11 Correct 3 ms 1516 KB Output is correct
12 Correct 3 ms 1520 KB Output is correct
13 Correct 3 ms 1584 KB Output is correct
14 Correct 4 ms 1584 KB Output is correct
15 Correct 135 ms 84732 KB Output is correct
16 Incorrect 56 ms 84732 KB Output isn't correct
17 Halted 0 ms 0 KB -