oj.uz

답안 #574501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574501 2022-06-08T15:54:19 Z Sohsoh84 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 131 ms 41668 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll LOG = 20;

int n, rt, par[MAXN][LOG], q, tin[MAXN], mn[MAXN], f[MAXN], t;
vector<int> adj[MAXN];
priority_queue<int> pq;
bool used[MAXN];

void dfs1(int v) {
	mn[v] = v;
	for (int u : adj[v]) {
		dfs1(u);
		mn[v] = min(mn[v], mn[u]);
	}
}

void dfs2(int v) {	
	tin[v] = ++t;
	f[t] = v;
	sort(all(adj[v]), [] (int i, int j) {
		return mn[i] > mn[j];
	});

	for (int u : adj[v])
		dfs2(u);
}

inline int add() {
	int v = f[pq.top()];
	pq.pop();

	used[v] = true;
	return v;
}

inline int remove(int v) {
	int ans = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		if (used[par[v][i]]) {
			ans ^= (1 << i);
			v = par[v][i];
		}	
	}

	used[v] = false;
	pq.push(tin[v]);
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> par[i][0];
		rt = (par[i][0] ? rt : i);
		pq.push(i);

		adj[par[i][0]].push_back(i);
	}

	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			par[v][i] = par[par[v][i - 1]][i - 1];

	dfs1(rt);
	dfs2(rt);

	while (q--) {
		int c, x;
		cin >> c >> x;

		if (c == 1) {
			int ans = 0;
			while (x--) ans = add();
			cout << ans << endl;
		} else {
			cout << remove(x) << endl;
		}
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 76 ms 31236 KB Output is correct
3 Correct 71 ms 31408 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23828 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 13 ms 23852 KB Output is correct
9 Correct 15 ms 24276 KB Output is correct
10 Correct 26 ms 25684 KB Output is correct
11 Correct 68 ms 31228 KB Output is correct
12 Correct 61 ms 31304 KB Output is correct
13 Correct 67 ms 31252 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 27208 KB Output is correct
2 Correct 114 ms 37812 KB Output is correct
3 Correct 79 ms 34676 KB Output is correct
4 Correct 55 ms 28208 KB Output is correct
5 Correct 46 ms 28108 KB Output is correct
6 Correct 49 ms 28104 KB Output is correct
7 Correct 50 ms 27476 KB Output is correct
8 Correct 38 ms 27168 KB Output is correct
9 Correct 96 ms 38152 KB Output is correct
10 Correct 95 ms 37720 KB Output is correct
11 Correct 88 ms 37752 KB Output is correct
12 Correct 112 ms 36292 KB Output is correct
13 Correct 78 ms 39336 KB Output is correct
14 Correct 70 ms 34764 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 31084 KB Output is correct
2 Correct 115 ms 36704 KB Output is correct
3 Correct 83 ms 38024 KB Output is correct
4 Correct 72 ms 35388 KB Output is correct
5 Correct 76 ms 35016 KB Output is correct
6 Correct 75 ms 35004 KB Output is correct
7 Correct 70 ms 34080 KB Output is correct
8 Correct 87 ms 37900 KB Output is correct
9 Correct 120 ms 38308 KB Output is correct
10 Correct 111 ms 37960 KB Output is correct
11 Correct 109 ms 37964 KB Output is correct
12 Correct 110 ms 36800 KB Output is correct
13 Correct 131 ms 41668 KB Output is correct
14 Correct 82 ms 34836 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 38488 KB Output is correct
2 Correct 116 ms 36748 KB Output is correct
3 Correct 97 ms 41460 KB Output is correct
4 Correct 113 ms 38524 KB Output is correct
5 Correct 104 ms 37912 KB Output is correct
6 Correct 93 ms 37952 KB Output is correct
7 Correct 112 ms 36808 KB Output is correct
8 Correct 88 ms 41456 KB Output is correct
9 Correct 71 ms 34696 KB Output is correct