oj.uz

Submission #872074

# Submission time Handle Problem Language Result Execution time Memory
872074 2023-11-12T09:14:31 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
28.6996 / 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];
vector<int> ad[N];
set<pii> ver, one[N], sq[SQ];
pii tree[N];

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

void dfs(int v) {
	sz[v] = 1;
	mn[v] = v;
	st[v] = s++;
	for (int u: ad[v]) {
		h[u] = h[v] + 1;
		dfs(u);
		mn[v] = min(mn[v], mn[u]);
		sz[v] += sz[u];
	}
}

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

void forSort() {
	for (int i = 0; i < n; i++)
		sort(ad[i].begin(), ad[i].end(), cmp);
	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;
}

void dfs2(int v) {
	for (int u: ad[v])
		dfs2(u);
	indx[v] = t++;
	
}

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

void output(int v) {
	int p, 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;
	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);
	forSort();
	dfs2(root);
	for (int i = 0; i < n; i++)
		ver.insert({indx[i], i});
	while (q--) {
		int t, v;
		cin >> t >> v;
		if (t == 1)
			add(v);
		else {
			v--;
			output(v);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'void output(int)':
ballmachine.cpp:96:20: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |  cout << h[v] - h[p] << '\n';
      |                 ~~~^

Subtask #1
13.4615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Runtime error 70 ms 42296 KB Execution killed with signal 11
3 Correct 64 ms 15396 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8628 KB Output is correct
6 Correct 3 ms 8884 KB Output is correct
7 Runtime error 10 ms 18012 KB Execution killed with signal 11
8 Correct 3 ms 8792 KB Output is correct
9 Runtime error 12 ms 19036 KB Execution killed with signal 11
10 Runtime error 31 ms 29276 KB Execution killed with signal 11
11 Runtime error 74 ms 51036 KB Execution killed with signal 11
12 Correct 55 ms 15188 KB Output is correct
13 Runtime error 50 ms 32300 KB Execution killed with signal 11

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12628 KB Output is correct
2 Runtime error 650 ms 131072 KB Execution killed with signal 9
3 Correct 67 ms 17740 KB Output is correct
4 Runtime error 280 ms 131072 KB Execution killed with signal 9
5 Runtime error 405 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1081 ms 32520 KB Time limit exceeded
7 Execution timed out 1051 ms 88596 KB Time limit exceeded
8 Correct 34 ms 12624 KB Output is correct
9 Runtime error 395 ms 131072 KB Execution killed with signal 9
10 Runtime error 687 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1035 ms 71868 KB Time limit exceeded
12 Runtime error 471 ms 131072 KB Execution killed with signal 9
13 Correct 81 ms 25684 KB Output is correct
14 Correct 72 ms 17784 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 282 ms 131072 KB Execution killed with signal 9
2 Runtime error 316 ms 131072 KB Execution killed with signal 9
3 Runtime error 284 ms 131072 KB Execution killed with signal 9
4 Runtime error 323 ms 131072 KB Execution killed with signal 9
5 Runtime error 314 ms 131072 KB Execution killed with signal 9
6 Runtime error 358 ms 131072 KB Execution killed with signal 9
7 Runtime error 313 ms 131072 KB Execution killed with signal 9
8 Runtime error 293 ms 131072 KB Execution killed with signal 9
9 Runtime error 302 ms 131072 KB Execution killed with signal 9
10 Runtime error 320 ms 131072 KB Execution killed with signal 9
11 Runtime error 313 ms 131072 KB Execution killed with signal 9
12 Runtime error 325 ms 131072 KB Execution killed with signal 9
13 Runtime error 344 ms 131072 KB Execution killed with signal 9
14 Correct 120 ms 21452 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 381 ms 131072 KB Execution killed with signal 9
2 Runtime error 315 ms 131072 KB Execution killed with signal 9
3 Correct 84 ms 27784 KB Output is correct
4 Runtime error 363 ms 131072 KB Execution killed with signal 9
5 Runtime error 358 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1049 ms 30292 KB Time limit exceeded
7 Runtime error 336 ms 131072 KB Execution killed with signal 9
8 Correct 101 ms 27724 KB Output is correct
9 Correct 63 ms 17868 KB Output is correct