oj.uz

답안 #25989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25989 2017-06-25T13:30:30 Z gs14004 우주 해적 (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(!cmp[i] && max(k - ed, 0ll) <= k - st) 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);
	}
	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]){
					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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 3 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 0 ms 31320 KB Output is correct
11 Correct 0 ms 31320 KB Output is correct
12 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 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 719 ms 31452 KB Output is correct
5 Correct 199 ms 31452 KB Output is correct
6 Correct 329 ms 31452 KB Output is correct
7 Correct 1836 ms 31452 KB Output is correct
8 Correct 296 ms 31452 KB Output is correct
9 Correct 749 ms 31460 KB Output is correct
10 Correct 203 ms 31452 KB Output is correct
11 Correct 0 ms 31452 KB Output is correct
12 Correct 689 ms 31452 KB Output is correct
13 Correct 296 ms 31452 KB Output is correct
14 Correct 183 ms 31452 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1316 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 33300 KB Execution timed out
2 Halted 0 ms 0 KB -