oj.uz

Submission #747652

# Submission time Handle Problem Language Result Execution time Memory
747652 2023-05-24T12:41:20 Z Dan4Life Space Pirate (JOI14_space_pirate) C++17
47 / 100
 960 ms 71376 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)3e3+2;
const int mxLg = 12;
const int LINF = (int)1e18+2;
int n, k, p[mxN], ans[mxN];
int vis[mxN], cyc[mxN], SZ[mxN];
int D[mxN][mxN], jmp[mxLg][mxN];
 
int getPath(int x, int k){
	if(D[x][cyc[x]] <= k)
		k-=D[x][cyc[x]], k%=SZ[cyc[x]], x = cyc[x];
	for(int i = 0; i<mxLg; i++)
		if((k>>i)&1) x = jmp[i][x];
	return x;
}
 
int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> p[i], jmp[0][i]=p[i];
	for(int i = 1; i < mxLg; i++)
		for(int j = 1; j <= n; j++)
			jmp[i][j] = jmp[i-1][jmp[i-1][j]];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			D[i][j] = LINF;
	for(int i = 1; i <= n; i++){
		int j = i, tot=0; vector<int> v; v.clear();
		while(!vis[j]) D[i][j] = tot++, v.push_back(j), vis[j]=1, j=p[j];
		for(auto u : v) cyc[u]=j, vis[u]=0; tot = 0;
		while(!vis[j]) vis[j]=1, j=p[j], tot++;
		for(auto u : v) SZ[u] = tot, vis[u]=0;
	}
	for(int a = 1; a <= n; a++){
		for(int b = 1; b <= n; b++){
			if(D[1][a]>=k) ans[getPath(1,k)]++;
			else{
				int xd = k-D[1][a]-1;
				if(D[b][a]>=xd) ans[getPath(b,xd)]++;
				else ans[getPath(b,xd%(D[b][a]+1))]++;
			}
		}
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}

Compilation message

space_pirate.cpp: In function 'int32_t main()':
space_pirate.cpp:32:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   32 |   for(auto u : v) cyc[u]=j, vis[u]=0; tot = 0;
      |   ^~~
space_pirate.cpp:32:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   32 |   for(auto u : v) cyc[u]=j, vis[u]=0; tot = 0;
      |                                       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 191 ms 71180 KB Output is correct
16 Correct 171 ms 71192 KB Output is correct
17 Correct 188 ms 71116 KB Output is correct
18 Correct 960 ms 71244 KB Output is correct
19 Correct 572 ms 71216 KB Output is correct
20 Correct 534 ms 71244 KB Output is correct
21 Correct 819 ms 71340 KB Output is correct
22 Correct 462 ms 71236 KB Output is correct
23 Correct 574 ms 71376 KB Output is correct
24 Correct 319 ms 71316 KB Output is correct
25 Correct 183 ms 71172 KB Output is correct
26 Correct 881 ms 71260 KB Output is correct
27 Correct 371 ms 71184 KB Output is correct
28 Correct 375 ms 71204 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 191 ms 71180 KB Output is correct
16 Correct 171 ms 71192 KB Output is correct
17 Correct 188 ms 71116 KB Output is correct
18 Correct 960 ms 71244 KB Output is correct
19 Correct 572 ms 71216 KB Output is correct
20 Correct 534 ms 71244 KB Output is correct
21 Correct 819 ms 71340 KB Output is correct
22 Correct 462 ms 71236 KB Output is correct
23 Correct 574 ms 71376 KB Output is correct
24 Correct 319 ms 71316 KB Output is correct
25 Correct 183 ms 71172 KB Output is correct
26 Correct 881 ms 71260 KB Output is correct
27 Correct 371 ms 71184 KB Output is correct
28 Correct 375 ms 71204 KB Output is correct
29 Runtime error 3 ms 468 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -