oj.uz

답안 #43672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43672 2018-03-19T09:59:11 Z gs14004 우주 해적 (JOI14_space_pirate) C++14
80 / 100
 2000 ms 42224 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);
		}
	}
}

void mod_gazua(int v, lint k, int s, int e){
	for(int i=s; i<=e; i++){
		ans[anc(v, k % i)]++;
	}
}

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);
			int c = lev[i] - lev[oneanc[i]];
			lint u = k - up[oneanc[i]] + 1 + lev[i] - lev[oneanc[i]];
			mod_gazua(i, u, c + 1, c + sz);
		}
	}
	for(int i=1; i<=n; i++){
		if(cmp[i] && cnt[i] != 2){
			int uci = up[cmp[i]];
			int vst = st, ved = min(1ll * ed, k);
			for(int j=vst; j<=ved; j++){
				int md = 0;
				if(j < uci) md = ed - st + 1 - uci + j + 1 + lev[i];
				else md = j - uci + 1 + lev[i];
				ans[anc(i, (k - j) % md)]++;
			}
		}
	}
	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:164: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:166: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 5544 KB Output is correct
4 Correct 7 ms 5620 KB Output is correct
5 Correct 6 ms 5668 KB Output is correct
6 Correct 6 ms 5668 KB Output is correct
7 Correct 6 ms 5668 KB Output is correct
8 Correct 6 ms 5668 KB Output is correct
9 Correct 6 ms 5668 KB Output is correct
10 Correct 7 ms 5668 KB Output is correct
11 Correct 6 ms 5668 KB Output is correct
12 Correct 6 ms 5668 KB Output is correct
13 Correct 5 ms 5668 KB Output is correct
14 Correct 6 ms 5668 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6636 KB Output is correct
2 Correct 8 ms 6636 KB Output is correct
3 Correct 21 ms 6652 KB Output is correct
4 Correct 75 ms 6804 KB Output is correct
5 Correct 17 ms 6804 KB Output is correct
6 Correct 194 ms 6804 KB Output is correct
7 Correct 338 ms 7052 KB Output is correct
8 Correct 106 ms 7052 KB Output is correct
9 Correct 318 ms 7052 KB Output is correct
10 Correct 73 ms 7052 KB Output is correct
11 Correct 8 ms 7052 KB Output is correct
12 Correct 65 ms 7052 KB Output is correct
13 Correct 83 ms 7052 KB Output is correct
14 Correct 140 ms 7052 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 42224 KB Output is correct
2 Correct 293 ms 42224 KB Output is correct
3 Correct 406 ms 42224 KB Output is correct
4 Correct 429 ms 42224 KB Output is correct
5 Correct 313 ms 42224 KB Output is correct
6 Correct 374 ms 42224 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1436 ms 42224 KB Output is correct
2 Correct 903 ms 42224 KB Output is correct
3 Correct 121 ms 42224 KB Output is correct
4 Execution timed out 2037 ms 42224 KB Time limit exceeded
5 Halted 0 ms 0 KB -