oj.uz

답안 #43671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43671 2018-03-19T09:54:59 Z gs14004 우주 해적 (JOI14_space_pirate) C++14
80 / 100
 2000 ms 42276 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){
			for(int j=1; j<=n; j++){
				if(cnt[j] == 2 && k >= up[j]){
					int md = 0;
					if(up[j] < up[cmp[i]]) md = ed - st + 1 - (up[cmp[i]] - up[j] - 1) + lev[i];
					else md = up[j] - up[cmp[i]] + 1 + lev[i];
					ans[anc(i, (k - up[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 7 ms 5604 KB Output is correct
3 Correct 7 ms 5604 KB Output is correct
4 Correct 6 ms 5604 KB Output is correct
5 Correct 7 ms 5692 KB Output is correct
6 Correct 7 ms 5692 KB Output is correct
7 Correct 7 ms 5692 KB Output is correct
8 Correct 6 ms 5692 KB Output is correct
9 Correct 7 ms 5692 KB Output is correct
10 Correct 7 ms 5692 KB Output is correct
11 Correct 5 ms 5692 KB Output is correct
12 Correct 6 ms 5692 KB Output is correct
13 Correct 6 ms 5692 KB Output is correct
14 Correct 7 ms 5692 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6692 KB Output is correct
2 Correct 15 ms 6692 KB Output is correct
3 Correct 30 ms 6740 KB Output is correct
4 Correct 85 ms 6884 KB Output is correct
5 Correct 25 ms 6900 KB Output is correct
6 Correct 245 ms 7048 KB Output is correct
7 Correct 352 ms 7128 KB Output is correct
8 Correct 120 ms 7128 KB Output is correct
9 Correct 325 ms 7144 KB Output is correct
10 Correct 78 ms 7144 KB Output is correct
11 Correct 11 ms 7144 KB Output is correct
12 Correct 66 ms 7144 KB Output is correct
13 Correct 103 ms 7144 KB Output is correct
14 Correct 160 ms 7144 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 42276 KB Output is correct
2 Correct 356 ms 42276 KB Output is correct
3 Correct 416 ms 42276 KB Output is correct
4 Correct 438 ms 42276 KB Output is correct
5 Correct 347 ms 42276 KB Output is correct
6 Correct 423 ms 42276 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2032 ms 42276 KB Time limit exceeded
2 Halted 0 ms 0 KB -