oj.uz

답안 #872227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872227 2023-11-12T14:33:46 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
40.2381 / 100
 1000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 7, SQ = 320;
int n, q, s, t, root, h[N], st[N], sz[N], mn[N], indx[N], it[N];
pii tree[N];
vector<int> ad[N];
set<pii> ver, one[N], sq[SQ];

void input() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		p--;
		if (p < 0)
			root = i;
		else
			ad[p].push_back(i);
	}
}

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

bool cmp(int u, int v) {
	return mn[u] < mn[v];
}

void dfs2(int v) {
	st[v] = s++;
	sz[v] = 1;
	for (int u: ad[v]) {
		h[u] = h[v] + 1;
		dfs2(u);
		sz[v] += sz[u];
	}
	indx[v] = t++;	
}

void secondProcess() {
	for (int i = 0; i < n; i++)
		tree[i] = {st[i], i};
	sort(tree, tree + n);
	for (int i = 0; i < n; i++)
		it[tree[i].second] = i;
	for (int i = 0; i < n; i++)
		ver.insert({indx[i], i});
}

void addTo(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++) 
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].insert({h[v], v});
		else {
			sq[i / SQ].insert({h[v], v});
			i += SQ - 1;
		}
}

void toErase(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++)
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].erase({h[v], v});
		else {
			sq[i / SQ].erase({h[v], v});
			i += SQ - 1;
		}
}

void add(int x) {	
	while (x--) {
		pii p = *ver.begin();
		addTo(p.second);
		ver.erase(ver.begin());
		if (x == 0)
			cout << p.second + 1 << '\n';
	}
}

void output(int v) {
	int p = -1, hi = INT_MAX, i = it[v];
	if (one[i].size()) {
		p = (*one[i].begin()).second;
		hi = h[(*one[i].begin()).second];
	}
	if (sq[i / SQ].size() && h[(*sq[i / SQ].begin()).second] < hi)
		p = (*sq[i / SQ].begin()).second;
	if (p < 0)
		while (true);
	cout << h[v] - h[p] << '\n';
	ver.insert({indx[p], p});
	toErase(p);
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	dfs(root);
	for (int i = 0; i < n; i++)
		sort(ad[i].begin(), ad[i].end(), cmp);
	dfs2(root);
	secondProcess();
	while (q--) {
		int t, v;
		cin >> t >> v;
		if (t == 1)
			add(v);
		else {
			v--;
			output(v);
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 185 ms 31828 KB Output is correct
3 Correct 52 ms 14416 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 10 ms 9260 KB Output is correct
8 Correct 3 ms 9176 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 36 ms 14908 KB Output is correct
11 Correct 178 ms 31316 KB Output is correct
12 Correct 51 ms 14416 KB Output is correct
13 Correct 466 ms 16268 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 11864 KB Output is correct
2 Runtime error 350 ms 131072 KB Execution killed with signal 9
3 Correct 62 ms 16848 KB Output is correct
4 Runtime error 846 ms 131072 KB Execution killed with signal 9
5 Runtime error 474 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1056 ms 48208 KB Time limit exceeded
7 Runtime error 774 ms 131072 KB Execution killed with signal 9
8 Correct 28 ms 11868 KB Output is correct
9 Runtime error 743 ms 131072 KB Execution killed with signal 9
10 Runtime error 372 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1075 ms 111892 KB Time limit exceeded
12 Runtime error 723 ms 131072 KB Execution killed with signal 9
13 Correct 71 ms 23244 KB Output is correct
14 Correct 78 ms 16844 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 377 ms 131072 KB Execution killed with signal 9
2 Runtime error 360 ms 131072 KB Execution killed with signal 9
3 Runtime error 306 ms 131072 KB Execution killed with signal 9
4 Runtime error 487 ms 131072 KB Execution killed with signal 9
5 Runtime error 344 ms 131072 KB Execution killed with signal 9
6 Runtime error 342 ms 131072 KB Execution killed with signal 9
7 Runtime error 338 ms 131072 KB Execution killed with signal 9
8 Runtime error 296 ms 131072 KB Execution killed with signal 9
9 Runtime error 790 ms 131072 KB Execution killed with signal 9
10 Runtime error 328 ms 131072 KB Execution killed with signal 9
11 Runtime error 336 ms 131072 KB Execution killed with signal 9
12 Runtime error 344 ms 131072 KB Execution killed with signal 9
13 Runtime error 620 ms 131072 KB Execution killed with signal 9
14 Correct 112 ms 20008 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 498 ms 131072 KB Execution killed with signal 9
2 Runtime error 343 ms 131072 KB Execution killed with signal 9
3 Correct 87 ms 25052 KB Output is correct
4 Runtime error 494 ms 131072 KB Execution killed with signal 9
5 Runtime error 337 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1020 ms 34688 KB Time limit exceeded
7 Runtime error 345 ms 131072 KB Execution killed with signal 9
8 Correct 82 ms 24860 KB Output is correct
9 Correct 62 ms 16844 KB Output is correct