oj.uz

답안 #116333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116333 2019-06-12T09:33:30 Z ZwariowanyMarcin Ball Machine (BOI13_ballmachine) C++14
100 / 100
 453 ms 30212 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


#define pb push_back
#define ld long double
#define fi first
#define se second
#define ll long long
#define ss(x) (int) x.size()
#define mp make_pair
#define FOR(i, n) for(int i = 1; n >= i; ++i)

using namespace std;
using namespace __gnu_pbds;

const int nax = 1e5 + 5, pod = (1 << 19), mod = 998244353;
const ll inf = 1e18;

int n, q;
int root;
vector <int> v[nax];
int black[nax], lca[nax][17];
int dp[nax];
int pr[nax];
int fre = 0;
int liczba[nax];

void dfs(int node) {
	dp[node] = node;
	for(auto it: v[node]) {
		dfs(it);
		dp[node] = min(dp[node], dp[it]);
		lca[it][0] = node;
	}
}

void go(int node) {
	vector <pair<int, int>> e;
	for(auto it: v[node]) {
		e.pb(mp(dp[it], it));
	}
	sort(e.begin(), e.end());
	for(auto it: e) {
		go(it.se);
	}
	pr[node] = fre++;
}

set <pair<int, int>> s;

int add() {
	pair<int, int> x = *s.begin();
	black[x.se] = 1;
	liczba[lca[x.se][0]]++;
	if(liczba[lca[x.se][0]] == ss(v[lca[x.se][0]]))
		s.insert(mp(pr[lca[x.se][0]], lca[x.se][0]));
	s.erase(s.begin());
	return x.se;
}
	


int main() {
	
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		int p;
		cin >> p;
		if(!p)
			root = i;
		else
			v[p].pb(i);
	}
	dfs(root);
	for(int j = 1; j <= 16; ++j)
		for(int i = 1; i <= n; ++i)
			lca[i][j] = lca[lca[i][j - 1]][j - 1];
	go(root);
	
	for(int i = 1; i <= n; ++i) 
		s.insert(mp(pr[i], i));
	while(q--) {
		int type;
		int k;
		cin >> type >> k;
		if(type == 1) {
			int res = -1;
			while(k--) {
				res = add();
			}
			cout << res << endl;
		}
		else {
			int w = k;
			int dis = 0;
			for(int i = 16; 0 <= i; --i) {
				int r = lca[w][i];
				if(!r)
					continue;
				if(black[r]) {
					w = r;
					dis += (1 << i);
				}
			}
			black[w] = 0;
			if(s.find(mp(pr[lca[w][0]], lca[w][0])) != s.end())
				s.erase(mp(pr[lca[w][0]], lca[w][0]));
			liczba[lca[w][0]]--;
			s.insert(mp(pr[w], w));
			cout << dis << endl;
		}
	}
			
			
	
	
	
	
		
	
    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 358 ms 13688 KB Output is correct
3 Correct 240 ms 13048 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 6 ms 2944 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 22 ms 3328 KB Output is correct
10 Correct 59 ms 5528 KB Output is correct
11 Correct 346 ms 13800 KB Output is correct
12 Correct 220 ms 13048 KB Output is correct
13 Correct 264 ms 13688 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 8056 KB Output is correct
2 Correct 410 ms 24084 KB Output is correct
3 Correct 256 ms 17356 KB Output is correct
4 Correct 207 ms 9680 KB Output is correct
5 Correct 208 ms 9604 KB Output is correct
6 Correct 200 ms 9764 KB Output is correct
7 Correct 224 ms 8412 KB Output is correct
8 Correct 146 ms 8056 KB Output is correct
9 Correct 394 ms 24280 KB Output is correct
10 Correct 440 ms 24028 KB Output is correct
11 Correct 351 ms 23928 KB Output is correct
12 Correct 405 ms 21364 KB Output is correct
13 Correct 290 ms 25980 KB Output is correct
14 Correct 238 ms 17380 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 13620 KB Output is correct
2 Correct 427 ms 21680 KB Output is correct
3 Correct 267 ms 24312 KB Output is correct
4 Correct 292 ms 19948 KB Output is correct
5 Correct 273 ms 19576 KB Output is correct
6 Correct 279 ms 19648 KB Output is correct
7 Correct 297 ms 17784 KB Output is correct
8 Correct 277 ms 24340 KB Output is correct
9 Correct 439 ms 24556 KB Output is correct
10 Correct 448 ms 24192 KB Output is correct
11 Correct 432 ms 24184 KB Output is correct
12 Correct 437 ms 21816 KB Output is correct
13 Correct 430 ms 30212 KB Output is correct
14 Correct 384 ms 18680 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 410 ms 24540 KB Output is correct
2 Correct 417 ms 21696 KB Output is correct
3 Correct 320 ms 29008 KB Output is correct
4 Correct 453 ms 24544 KB Output is correct
5 Correct 443 ms 24184 KB Output is correct
6 Correct 351 ms 24184 KB Output is correct
7 Correct 452 ms 21752 KB Output is correct
8 Correct 331 ms 29112 KB Output is correct
9 Correct 247 ms 17476 KB Output is correct