oj.uz

Submission #25817

# Submission time Handle Problem Language Result Execution time Memory
25817 2017-06-24T08:36:03 Z 범수사생팬(#1085) Space Pirate (JOI14_space_pirate) C++14
10 / 100
 2000 ms 34484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint k;
int n, a[100005];
int par[60][100005];
vector<int> gph[100005];

int anc(int x, lint k){
	for(int i=0; k; i++){
		if((k >> i) & 1){
			k ^= (1ll << i);
			x = par[i][x];
		}
	}
	return x;
}

lint ans[100005];

int cnt[100005], up[100005], lev[100005], cmp[100005];
int din[100005], dout[100005], piv;

bool sub(int s, int t){
	return din[s] <= din[t] && dout[t] <= dout[s];
}

void dfs(int x, int p){
	din[x] = piv++;
	for(auto &i : gph[x]){
		if(i != p && cnt[i] != 2){
			lev[i] = lev[x] + 1;
			cmp[i] = cmp[x];
			dfs(i, x);
		}
	}
	dout[x] = piv;
}

int main(){
	scanf("%d %lld",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		gph[a[i]].push_back(i);
		par[0][i] = a[i];
	}
	for(int i=1; i<60; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	int idx = 0, st = 1e9, ed = -1e9;
	for(int p=1; cnt[p]<2; p=a[p]) cnt[p]++;
	for(int p=1; !up[p]; p=a[p]) up[p] = ++idx;
	for(int i=1; i<=n; i++){
		if(cnt[i] == 2){
			st = min(st, up[i]);
			ed = max(ed, up[i]);
			cmp[i] = i;
			dfs(i, -1);
		}
	}
	for(int i=1; i<=n; i++){
		if(cnt[i] == 0 || k < up[i]){
			ans[anc(1, k)] += n;
			continue;
		}
		if(cnt[i] == 1){
			for(int j=1; j<=n; j++){
				lint t = k - up[i];
				if(sub(i, j)) t %= lev[j] - lev[i] + 1;
				ans[anc(j, t)]++;
			}
		}
		if(cnt[i] == 2){
			for(int j=1; j<=n; j++){
				lint t = k - up[i];
				if(cmp[j]){
					if(up[i] < up[cmp[j]]) t %= (ed - st + 1) - (up[cmp[j]] - up[i] - 1) + lev[j];
					else t %= (up[i] - up[cmp[j]] + 1) + lev[j];
				}
				ans[anc(j, t)]++;
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:44:24: 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:46:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31448 KB Output is correct
2 Correct 0 ms 31316 KB Output is correct
3 Correct 29 ms 31448 KB Output is correct
4 Correct 936 ms 31448 KB Output is correct
5 Correct 1002 ms 31448 KB Output is correct
6 Correct 423 ms 31448 KB Output is correct
7 Execution timed out 2000 ms 31448 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 34484 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 33296 KB Execution timed out
2 Halted 0 ms 0 KB -