Submission #25834

#	Time	Username	Problem	Language	Result	Execution time	Memory
25834		gs14004	Space Pirate (JOI14_space_pirate)	C++11	10 / 100	2000 ms	34488 KiB

space_pirate

#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(!cmp[i]){
			if(max(k - ed, 0ll) <= k - st) update(i, max(k - ed, 0ll), k - st, 1);
		}
	}
	int c = n - count(cmp + 1, cmp + n + 1, 0);
	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)) t %= lev[j] - lev[i] + 1;
				ans[anc(j, t)]++;
			}
		}
		if(cnt[i] == 2){
			if(n <= 3000){
				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)]++;
					}
				}
			}
		}
	}
	if(n > 3000){
		int c = n - count(cmp + 1, cmp + n + 1, 0);
		for(int j=1; j<=n; j++){
			if(cmp[j]) ans[j] += min(1ll * c, k);
		}
	}
	for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:81:6: warning: unused variable 'c' [-Wunused-variable]
  int c = n - count(cmp + 1, cmp + n + 1, 0);
      ^
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 / 10
• Subtask 2: 0 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20