oj.uz

Submission #25998

# Submission time Handle Problem Language Result Execution time Memory
25998 2017-06-25T17:04:40 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 && n <= 3000){
			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 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 119 ms 31452 KB Output is correct
5 Correct 46 ms 31452 KB Output is correct
6 Correct 226 ms 31452 KB Output is correct
7 Correct 1896 ms 31452 KB Output is correct
8 Correct 319 ms 31452 KB Output is correct
9 Correct 743 ms 31460 KB Output is correct
10 Correct 219 ms 31452 KB Output is correct
11 Correct 3 ms 31452 KB Output is correct
12 Correct 76 ms 31452 KB Output is correct
13 Correct 276 ms 31452 KB Output is correct
14 Correct 153 ms 31452 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1656 ms 33300 KB Output isn't correct
2 Halted 0 ms 0 KB -