oj.uz

Submission #872223

# Submission time Handle Problem Language Result Execution time Memory
872223 2023-11-12T14:22:50 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, hi = INT_MAX, i = it[v];
	if (sq[i / SQ].empty() && one[i].empty()) 
		while (true)
			;
	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);
	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);
		}
	}
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 182 ms 31928 KB Output is correct
3 Correct 51 ms 14420 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 9252 KB Output is correct
8 Correct 3 ms 9048 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 35 ms 14928 KB Output is correct
11 Correct 179 ms 31316 KB Output is correct
12 Correct 57 ms 14672 KB Output is correct
13 Correct 517 ms 16212 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11868 KB Output is correct
2 Runtime error 349 ms 131072 KB Execution killed with signal 9
3 Correct 61 ms 16844 KB Output is correct
4 Runtime error 849 ms 131072 KB Execution killed with signal 9
5 Runtime error 474 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1049 ms 48420 KB Time limit exceeded
7 Runtime error 744 ms 131072 KB Execution killed with signal 9
8 Correct 26 ms 11868 KB Output is correct
9 Runtime error 657 ms 131072 KB Execution killed with signal 9
10 Runtime error 341 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1072 ms 112116 KB Time limit exceeded
12 Runtime error 666 ms 131072 KB Execution killed with signal 9
13 Correct 71 ms 23116 KB Output is correct
14 Correct 67 ms 16848 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 131072 KB Execution killed with signal 9
2 Runtime error 353 ms 131072 KB Execution killed with signal 9
3 Runtime error 322 ms 131072 KB Execution killed with signal 9
4 Runtime error 489 ms 131072 KB Execution killed with signal 9
5 Runtime error 328 ms 131072 KB Execution killed with signal 9
6 Runtime error 336 ms 131072 KB Execution killed with signal 9
7 Runtime error 327 ms 131072 KB Execution killed with signal 9
8 Runtime error 289 ms 131072 KB Execution killed with signal 9
9 Runtime error 767 ms 131072 KB Execution killed with signal 9
10 Runtime error 321 ms 131072 KB Execution killed with signal 9
11 Runtime error 336 ms 131072 KB Execution killed with signal 9
12 Runtime error 341 ms 131072 KB Execution killed with signal 9
13 Runtime error 581 ms 131072 KB Execution killed with signal 9
14 Correct 126 ms 20080 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 501 ms 131072 KB Execution killed with signal 9
2 Runtime error 349 ms 131072 KB Execution killed with signal 9
3 Correct 79 ms 24916 KB Output is correct
4 Runtime error 509 ms 131072 KB Execution killed with signal 9
5 Runtime error 331 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1063 ms 34672 KB Time limit exceeded
7 Runtime error 337 ms 131072 KB Execution killed with signal 9
8 Correct 82 ms 24912 KB Output is correct
9 Correct 62 ms 16792 KB Output is correct