oj.uz

답안 #43645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43645 2018-03-19T02:30:33 Z koosaga 우주 해적 (JOI14_space_pirate) C++14
80 / 100
 549 ms 44748 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;
}

vector<pi> qry[100005];
int deg[100005], levl[100005], cmpl[100005];
int cn[100005], cg[100005], csz[100005], ch[100005], rev[100005], piv2, piv3;
lint dx1[100005], dx2[100005];

void dfs2(int x, int p){
	for(auto &i : gph[x]){
		if(i != p && !deg[i]){
			levl[i] = levl[x] + 1;
			cmpl[i] = cmpl[x];
			dfs2(i, x);
		}
	}
}

void dfs3(int x, int p){
	for(auto &i : gph[x]){
		if(i != p && !deg[i]){
			dfs3(i, x);
			dx1[x] += dx1[i];
		}
	}
}

void clear_line(){
	queue<int> que;
	for(int i=1; i<=n; i++){
		if(!deg[i]) que.push(i);
	}
	while(!que.empty()){
		int x = que.front();
		que.pop();
		deg[a[x]]--;
		if(deg[a[x]] == 0) que.push(a[x]);
	}
	for(int i=1; i<=n; i++){
		if(deg[i]){
			cmpl[i] = i;
			dfs2(i, -1);
		}
	}
	for(int i=1; i<=n; i++){
		if(deg[i] && !cn[i]){
			piv2++;
			ch[piv2] = i;
			for(int j=i; !cn[j]; j=a[j]){
				cg[j] = piv2;
				cn[j] = ++piv3;
				csz[piv2]++;
			}
		}
	}
	for(int i=1; i<=n; i++){
		rev[cn[i]] = i;
	}
	for(int i=1; i<=n; i++){
		for(auto &j : qry[i]){
			int cnt = j.first;
			int len = j.second;
			if(len > levl[i]){
				dx1[i] += cnt;
				dx1[cmpl[i]] -= cnt;
				len -= levl[i];
				int compidx = cg[cmpl[i]];
				int compnum = cn[cmpl[i]];
				int compsize = csz[compidx];
				int comphead = ch[compidx];
				if(compnum + len - 1 >= compsize + cn[comphead]){
					dx2[compnum] += cnt;
					dx2[cn[comphead] + compsize] -= cnt;
					len -= compsize + cn[comphead] - compnum;
					dx2[cn[comphead]] += 1ll * cnt * (len / compsize);
					dx2[cn[comphead] + compsize] -= 1ll * cnt * (len / compsize);
					len %= compsize;
					dx2[cn[comphead]] += cnt;
					dx2[cn[comphead] + len] -= cnt;
				}
				else{
					dx2[compnum] += cnt;
					dx2[compnum + len] -= cnt;
				}
			}
			else{
				dx1[i] += cnt;
				dx1[anc(i, len)] -= cnt;
			}
		}
	}
	for(int i=1; i<=piv3; i++){
		dx2[i] += dx2[i-1];
		if(deg[i]) dfs3(i, -1);
	}
	for(int i=1; i<=n; i++){
		if(deg[i]) ans[i] += dx2[cn[i]];
		ans[i] += dx1[i];
	}
}

void update(int s, lint l1, lint l2, int x){
	s = anc(s, l1);
	qry[s].push_back(pi(x, l2 - l1 + 1));
}

int oneanc[100005];

void dfs4(int x, int p){
	for(auto &i : gph[x]){
		if(cnt[i] != 1 && i != p){
			oneanc[i] = oneanc[x];
			dfs4(i, x);
		}
	}
}

int main(){
	scanf("%d %lld",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		deg[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);
		}
		if(cnt[i] == 1){
			oneanc[i] = i;
			dfs4(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;
				}
			}
		}
		if(oneanc[i] > 0){
			lint ved = k - up[oneanc[i]];
			lint vst = k - st + 1;
			vst = max(vst, 0ll);
			if(vst <= ved) update(i, vst, ved, -1);
			int sz = (int)min(1ll * st - up[oneanc[i]], k - up[oneanc[i]] + 1);
			for(int j=1; j<=sz; ){
				int c = j + lev[i] - lev[oneanc[i]];
				lint u = k - up[oneanc[i]] + 1 - j;
				ans[anc(i, u % c)]++;
				j++;
				//int nxt = min(u % c + 1, 1ll * sz + 1 - j);
				//update(i, u % c - nxt + 1, u % c, 1);
				//j += nxt;
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(k < up[i] || cnt[i] == 0 || n > 3000) continue;
		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)]++;
				}
			}
		}
	}
	clear_line();
	for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:158: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:160: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 6 ms 5368 KB Output is correct
2 Correct 6 ms 5476 KB Output is correct
3 Correct 6 ms 5712 KB Output is correct
4 Correct 5 ms 5712 KB Output is correct
5 Correct 7 ms 5712 KB Output is correct
6 Correct 5 ms 5712 KB Output is correct
7 Correct 5 ms 5764 KB Output is correct
8 Correct 6 ms 5804 KB Output is correct
9 Correct 6 ms 5804 KB Output is correct
10 Correct 6 ms 5804 KB Output is correct
11 Correct 5 ms 5804 KB Output is correct
12 Correct 5 ms 5804 KB Output is correct
13 Correct 5 ms 5804 KB Output is correct
14 Correct 5 ms 5804 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 6792 KB Output is correct
2 Correct 10 ms 6792 KB Output is correct
3 Correct 21 ms 6808 KB Output is correct
4 Correct 98 ms 7048 KB Output is correct
5 Correct 44 ms 7048 KB Output is correct
6 Correct 223 ms 7104 KB Output is correct
7 Correct 354 ms 7400 KB Output is correct
8 Correct 113 ms 7400 KB Output is correct
9 Correct 337 ms 7400 KB Output is correct
10 Correct 79 ms 7400 KB Output is correct
11 Correct 10 ms 7400 KB Output is correct
12 Correct 83 ms 7400 KB Output is correct
13 Correct 96 ms 7400 KB Output is correct
14 Correct 116 ms 7400 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 43192 KB Output is correct
2 Correct 360 ms 43192 KB Output is correct
3 Correct 408 ms 43192 KB Output is correct
4 Correct 435 ms 44644 KB Output is correct
5 Correct 330 ms 44644 KB Output is correct
6 Correct 384 ms 44748 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 338 ms 44748 KB Output isn't correct
2 Halted 0 ms 0 KB -