oj.uz

답안 #26003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26003 2017-06-25T18:37:22 Z gs14004 우주 해적 (JOI14_space_pirate) C++14
80 / 100
 1846 ms 44560 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];
				int p = cmpl[i];
				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 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);
		}
	}
	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;
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(k < up[i] || cnt[i] == 0 || n > 3000) 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] && 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 'void clear_line()':
space_pirate.cpp:110:9: warning: unused variable 'p' [-Wunused-variable]
     int p = cmpl[i];
         ^
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:148: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:150: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 0 ms 38356 KB Output is correct
2 Correct 0 ms 38356 KB Output is correct
3 Correct 0 ms 38356 KB Output is correct
4 Correct 3 ms 38356 KB Output is correct
5 Correct 3 ms 38356 KB Output is correct
6 Correct 0 ms 38356 KB Output is correct
7 Correct 0 ms 38356 KB Output is correct
8 Correct 3 ms 38356 KB Output is correct
9 Correct 3 ms 38356 KB Output is correct
10 Correct 3 ms 38356 KB Output is correct
11 Correct 0 ms 38356 KB Output is correct
12 Correct 0 ms 38356 KB Output is correct
13 Correct 0 ms 38356 KB Output is correct
14 Correct 3 ms 38356 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 38488 KB Output is correct
2 Correct 3 ms 38492 KB Output is correct
3 Correct 19 ms 38488 KB Output is correct
4 Correct 113 ms 38488 KB Output is correct
5 Correct 39 ms 38488 KB Output is correct
6 Correct 219 ms 38488 KB Output is correct
7 Correct 1846 ms 38488 KB Output is correct
8 Correct 273 ms 38488 KB Output is correct
9 Correct 749 ms 38496 KB Output is correct
10 Correct 193 ms 38488 KB Output is correct
11 Correct 0 ms 38488 KB Output is correct
12 Correct 79 ms 38488 KB Output is correct
13 Correct 239 ms 38488 KB Output is correct
14 Correct 139 ms 38488 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 433 ms 44560 KB Output is correct
2 Correct 349 ms 41524 KB Output is correct
3 Correct 289 ms 43108 KB Output is correct
4 Correct 376 ms 44560 KB Output is correct
5 Correct 369 ms 41524 KB Output is correct
6 Correct 339 ms 43240 KB Output is correct

Subtask #4
0 / 20.0

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