oj.uz

답안 #255587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255587 2020-08-01T11:49:26 Z Saboon Ball Machine (BOI13_ballmachine) C++14
100 / 100
 743 ms 23800 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e5 + 10;

vector<int> t[maxn];
int mnm[maxn], ft[maxn], pos[maxn], Time = 1;
int par[maxn][20];
int seg[4*maxn], lazy[4*maxn];

void shift(int,int,int);

int get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return seg[id];
	shift(id,L,R);
	int mid = (L + R) >> 1;
	return get(2*id+0, L, mid, l, r) + get(2*id+1, mid, R, l, r);
}

void change(int id, int L, int R, int l, int r, int val){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id] = (R-L) * val;
		lazy[id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	shift(id,L,R);
	change(2*id+0, L, mid, l, r, val);
	change(2*id+1, mid, R, l, r, val);
	seg[id] = seg[2*id+0] + seg[2*id+1];
}

void shift(int id, int L, int R){
	if (lazy[id] == -1)
		return;
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, L, mid, lazy[id]);
	change(2*id+1, mid, R, mid, R, lazy[id]);
	lazy[id] = -1;
}

void dfs(int v){
	for (auto u : t[v])
		dfs(u);
	ft[v] = Time;
	pos[Time++] = v;
}

int dfsinit(int v){
	mnm[v] = v;
	for (auto u : t[v])
		mnm[v] = min(mnm[v], dfsinit(u));
	sort(t[v].begin(), t[v].end(), [](int x, int y){ return mnm[x] < mnm[y]; });
	return mnm[v];
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	int root = -1;
	memset(par, -1, sizeof par);
	for (int i = 1; i <= n; i++){
		int p;
		cin >> p;
		if (p == 0)
			root = i;
		else{
			t[p].push_back(i);
			par[i][0] = p;
		}
	}
	for (int i = 1; i <= 17; i++)
		for (int v = 1; v <= n; v++)
			if (par[v][i-1] != -1)
				par[v][i] = par[par[v][i-1]][i-1];
	dfsinit(root);
	dfs(root);
	memset(lazy, -1, sizeof lazy);
	while (q --){
		int type, x;
		cin >> type >> x;
		if (type == 1){
			int lo = 0, hi = n+1;
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (mid - get(1,1,n+1,1,mid+1) >= x)
					hi = mid;
				else
					lo = mid;
			}
			change(1,1,n+1,1,hi+1,1);
			cout << pos[hi] << '\n';
		}
		else{
			int ans = 0;
			for (int i = 17; i >= 0; i--)
				if (par[x][i] != -1 and get(1,1,n+1,ft[par[x][i]],ft[par[x][i]]+1) == 1)
					x = par[x][i], ans += (1 << i);
			cout << ans << '\n';
			change(1,1,n+1,ft[x],ft[x]+1,0);
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 367 ms 15608 KB Output is correct
3 Correct 432 ms 15296 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 8 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 34 ms 12288 KB Output is correct
10 Correct 78 ms 12928 KB Output is correct
11 Correct 361 ms 15480 KB Output is correct
12 Correct 427 ms 15412 KB Output is correct
13 Correct 359 ms 15224 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 14584 KB Output is correct
2 Correct 656 ms 19724 KB Output is correct
3 Correct 355 ms 15860 KB Output is correct
4 Correct 354 ms 14968 KB Output is correct
5 Correct 423 ms 14968 KB Output is correct
6 Correct 415 ms 14840 KB Output is correct
7 Correct 418 ms 14456 KB Output is correct
8 Correct 342 ms 14584 KB Output is correct
9 Correct 623 ms 19968 KB Output is correct
10 Correct 700 ms 19448 KB Output is correct
11 Correct 647 ms 18940 KB Output is correct
12 Correct 623 ms 18168 KB Output is correct
13 Correct 513 ms 21832 KB Output is correct
14 Correct 344 ms 15988 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 16376 KB Output is correct
2 Correct 675 ms 19152 KB Output is correct
3 Correct 435 ms 21496 KB Output is correct
4 Correct 366 ms 18896 KB Output is correct
5 Correct 406 ms 18424 KB Output is correct
6 Correct 407 ms 18424 KB Output is correct
7 Correct 399 ms 17400 KB Output is correct
8 Correct 430 ms 21344 KB Output is correct
9 Correct 598 ms 20472 KB Output is correct
10 Correct 669 ms 19960 KB Output is correct
11 Correct 652 ms 19960 KB Output is correct
12 Correct 658 ms 18936 KB Output is correct
13 Correct 703 ms 23800 KB Output is correct
14 Correct 349 ms 16884 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 635 ms 20132 KB Output is correct
2 Correct 670 ms 18680 KB Output is correct
3 Correct 545 ms 22776 KB Output is correct
4 Correct 640 ms 20052 KB Output is correct
5 Correct 743 ms 19704 KB Output is correct
6 Correct 640 ms 18936 KB Output is correct
7 Correct 669 ms 18680 KB Output is correct
8 Correct 555 ms 22624 KB Output is correct
9 Correct 362 ms 15860 KB Output is correct