oj.uz

Submission #25806

# Submission time Handle Problem Language Result Execution time Memory
25806 2017-06-24T07:55:46 Z 범수사생팬(#1085) Space Pirate (JOI14_space_pirate) C++14
0 / 100
 59 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 ^= (1 << 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] == 1){
			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++){
				if(sub(i, j)){
					lint t = k - up[i] + 1;
					t %= lev[j] - lev[i] + 1;
					if(t == 0) ans[i]++;
					else ans[anc(j, t - 1)]++;
				}
				else{
					ans[anc(j, k - up[i])]++;
				}
			}
		}
		if(cnt[i] == 2){
			for(int j=1; j<=n; j++){
				continue;
				if(cmp[j] == 0){
					ans[anc(j, k - up[i])]++;
				}
				else{
					if(up[i] < up[cmp[j]]){
						lint t = k - up[i] + 1;
						t %= (ed - st + 1) - (up[cmp[j]] - up[i] - 1) + lev[j];
						if(t == 0) ans[i]++;
						else ans[anc(j, t - 1)]++;
					}
					else{
						lint t = k - up[i] + 1;
						t %= (up[i] - up[cmp[j]] + 1) + lev[j];
						if(t == 0) ans[i]++;
						else ans[anc(j, t - 1)]++;
					}
				}
			}
		}
	}
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 31316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 31448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 34484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 33296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -