oj.uz

Submission #25997

# Submission time Handle Problem Language Result Execution time Memory
25997 2017-06-25T17:04:09 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);
				lint cnt = ed - st + 2 - j + k - up[i];
				for(int it=0; ; it++){
					int p = (k - up[i]) % j - j + 1 + it * j;
					int q = (k - up[i]) % j + it * j;
					if(p >= iter) break;
					int nxt = anc(i, cnt - ((k - up[i] - q) / j) * j);
					ans[nxt] += min(q, iter - 1) - max(0, p) + 1;
				}
			}
		}
	}
	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 0 ms 31320 KB Output is correct
9 Correct 0 ms 31320 KB Output is correct
10 Correct 3 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 16 ms 31452 KB Output is correct
2 Correct 3 ms 31320 KB Output is correct
3 Correct 19 ms 31452 KB Output is correct
4 Correct 116 ms 31452 KB Output is correct
5 Correct 43 ms 31452 KB Output is correct
6 Correct 209 ms 31452 KB Output is correct
7 Correct 1713 ms 31452 KB Output is correct
8 Correct 326 ms 31452 KB Output is correct
9 Correct 729 ms 31464 KB Output is correct
10 Correct 199 ms 31452 KB Output is correct
11 Correct 0 ms 31452 KB Output is correct
12 Correct 76 ms 31452 KB Output is correct
13 Correct 236 ms 31452 KB Output is correct
14 Correct 149 ms 31452 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1309 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 -