oj.uz

Submission #25996

# Submission time Handle Problem Language Result Execution time Memory
25996 2017-06-25T16:57:52 Z gs14004 Space Pirate (JOI14_space_pirate) C++14
47 / 100
 2000 ms 34488 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;
}

void update(int s, lint l1, lint l2, int x){
	s = anc(s, l1);
	while(l1 <= l2){
		ans[s]+=x;
		s = a[s];
		l1++;
	}
}

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);
		}
	}
	ans[anc(1, k)] += n * (max(0ll, ed - k) + count(cnt + 1, cnt + n + 1, 0));
	for(int i=1; i<=n; i++){
		if(max(k - ed, 0ll) <= k - st && cmp[i] == 0) update(i, max(k - ed, 0ll), k - st, 1);
		if(max(k - st + 1, 0ll) <= k - 1) update(i, max(k - st + 1, 0ll), k - 1, 1);
		if(up[i] == st && up[i] <= k){
			for(int j=1; j<=ed-st+1; j++){
				int iter = min(k - up[i] + 1, ed - st + 1ll);
				for(int l=0; l<iter; l++){
					int nxt = anc(i, l + ed - st + 2 - j + (k - up[i] - l) % j);
					ans[nxt]++;
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(k < up[i] || cnt[i] == 0) continue;
		if(cnt[i] == 1){
			for(int j=1; j<=n; j++){
				lint t = k - up[i];
				if(sub(i, j)){
					ans[anc(j, t)]--;
					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] && cnt[j] != 2){
					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:53: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:55: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 0 ms 31320 KB Output is correct
2 Correct 0 ms 31320 KB Output is correct
3 Correct 0 ms 31320 KB Output is correct
4 Correct 0 ms 31320 KB Output is correct
5 Correct 0 ms 31320 KB Output is correct
6 Correct 0 ms 31320 KB Output is correct
7 Correct 0 ms 31320 KB Output is correct
8 Correct 3 ms 31320 KB Output is correct
9 Correct 3 ms 31320 KB Output is correct
10 Correct 0 ms 31320 KB Output is correct
11 Correct 0 ms 31320 KB Output is correct
12 Correct 0 ms 31320 KB Output is correct
13 Correct 0 ms 31320 KB Output is correct
14 Correct 0 ms 31320 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31452 KB Output is correct
2 Correct 0 ms 31320 KB Output is correct
3 Correct 16 ms 31452 KB Output is correct
4 Correct 366 ms 31452 KB Output is correct
5 Correct 129 ms 31452 KB Output is correct
6 Correct 269 ms 31452 KB Output is correct
7 Correct 1859 ms 31452 KB Output is correct
8 Correct 273 ms 31452 KB Output is correct
9 Correct 759 ms 31464 KB Output is correct
10 Correct 196 ms 31452 KB Output is correct
11 Correct 3 ms 31452 KB Output is correct
12 Correct 363 ms 31452 KB Output is correct
13 Correct 259 ms 31452 KB Output is correct
14 Correct 173 ms 31452 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1359 ms 34488 KB Output is correct
2 Execution timed out 2000 ms 34488 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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