oj.uz

Submission #747648

# Submission time Handle Problem Language Result Execution time Memory
747648 2023-05-24T12:38:48 Z Dan4Life Space Pirate (JOI14_space_pirate) C++17
47 / 100
 897 ms 71628 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)3e3+10;
const int mxLg = 13;
const int LINF = (int)1e18+10;
int n, k, p[mxN], ans[mxN], vis[mxN], cyc[mxN], SZ[mxN];
int dis[mxN][mxN], jmp[mxLg][mxN];
 
int getPath(int x, int k){
	if(k==0) return x;
	if(dis[x][cyc[x]] <= k)
		k-=dis[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++)
			dis[i][j] = LINF;
	for(int i = 1; i <= n; i++){
		int j = i, tot=0; vector<int> v; v.clear();
		while(!vis[j]) dis[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;
	}
	int def = getPath(1,k);
	for(int a = 1; a <= n; a++){
		for(int b = 1; b <= n; b++){
			if(dis[1][a]>=k) ans[def]++;
			else{
				int xd = k-dis[1][a]-1;
				if(dis[b][a]>=xd) ans[getPath(b,xd)]++;
				else ans[getPath(b,xd%(dis[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 73 ms 71404 KB Output is correct
16 Correct 53 ms 71400 KB Output is correct
17 Correct 84 ms 71320 KB Output is correct
18 Correct 897 ms 71628 KB Output is correct
19 Correct 529 ms 71424 KB Output is correct
20 Correct 477 ms 71564 KB Output is correct
21 Correct 825 ms 71456 KB Output is correct
22 Correct 405 ms 71456 KB Output is correct
23 Correct 586 ms 71628 KB Output is correct
24 Correct 268 ms 71456 KB Output is correct
25 Correct 57 ms 71420 KB Output is correct
26 Correct 868 ms 71476 KB Output is correct
27 Correct 304 ms 71372 KB Output is correct
28 Correct 320 ms 71432 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 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 73 ms 71404 KB Output is correct
16 Correct 53 ms 71400 KB Output is correct
17 Correct 84 ms 71320 KB Output is correct
18 Correct 897 ms 71628 KB Output is correct
19 Correct 529 ms 71424 KB Output is correct
20 Correct 477 ms 71564 KB Output is correct
21 Correct 825 ms 71456 KB Output is correct
22 Correct 405 ms 71456 KB Output is correct
23 Correct 586 ms 71628 KB Output is correct
24 Correct 268 ms 71456 KB Output is correct
25 Correct 57 ms 71420 KB Output is correct
26 Correct 868 ms 71476 KB Output is correct
27 Correct 304 ms 71372 KB Output is correct
28 Correct 320 ms 71432 KB Output is correct
29 Runtime error 2 ms 468 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -