oj.uz

답안 #747644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747644 2023-05-24T12:35:52 Z Dan4Life 우주 해적 (JOI14_space_pirate) C++17
47 / 100
 934 ms 71500 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]>=k) 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 74 ms 71392 KB Output is correct
16 Correct 55 ms 71424 KB Output is correct
17 Correct 84 ms 71408 KB Output is correct
18 Correct 934 ms 71456 KB Output is correct
19 Correct 532 ms 71432 KB Output is correct
20 Correct 479 ms 71456 KB Output is correct
21 Correct 866 ms 71460 KB Output is correct
22 Correct 408 ms 71500 KB Output is correct
23 Correct 597 ms 71496 KB Output is correct
24 Correct 289 ms 71424 KB Output is correct
25 Correct 57 ms 71360 KB Output is correct
26 Correct 847 ms 71472 KB Output is correct
27 Correct 310 ms 71372 KB Output is correct
28 Correct 325 ms 71452 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 74 ms 71392 KB Output is correct
16 Correct 55 ms 71424 KB Output is correct
17 Correct 84 ms 71408 KB Output is correct
18 Correct 934 ms 71456 KB Output is correct
19 Correct 532 ms 71432 KB Output is correct
20 Correct 479 ms 71456 KB Output is correct
21 Correct 866 ms 71460 KB Output is correct
22 Correct 408 ms 71500 KB Output is correct
23 Correct 597 ms 71496 KB Output is correct
24 Correct 289 ms 71424 KB Output is correct
25 Correct 57 ms 71360 KB Output is correct
26 Correct 847 ms 71472 KB Output is correct
27 Correct 310 ms 71372 KB Output is correct
28 Correct 325 ms 71452 KB Output is correct
29 Runtime error 2 ms 468 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -