oj.uz

Submission #872224

# Submission time Handle Problem Language Result Execution time Memory
872224 2023-11-12T14:25:10 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--) {
		if (ver.empty())
			while (true)
				;
		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 (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 3 ms 8796 KB Output is correct
2 Correct 181 ms 31748 KB Output is correct
3 Correct 51 ms 14368 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 10 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 35 ms 14924 KB Output is correct
11 Correct 175 ms 31312 KB Output is correct
12 Correct 51 ms 14364 KB Output is correct
13 Correct 457 ms 16212 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11868 KB Output is correct
2 Runtime error 337 ms 131072 KB Execution killed with signal 9
3 Correct 65 ms 16788 KB Output is correct
4 Runtime error 853 ms 131072 KB Execution killed with signal 9
5 Runtime error 469 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1054 ms 48428 KB Time limit exceeded
7 Runtime error 802 ms 131072 KB Execution killed with signal 9
8 Correct 30 ms 11816 KB Output is correct
9 Runtime error 679 ms 131072 KB Execution killed with signal 9
10 Runtime error 339 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1057 ms 111956 KB Time limit exceeded
12 Runtime error 664 ms 131072 KB Execution killed with signal 9
13 Correct 74 ms 23124 KB Output is correct
14 Correct 61 ms 16848 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 372 ms 131072 KB Execution killed with signal 9
2 Runtime error 341 ms 131072 KB Execution killed with signal 9
3 Runtime error 290 ms 131072 KB Execution killed with signal 9
4 Runtime error 493 ms 131072 KB Execution killed with signal 9
5 Runtime error 338 ms 131072 KB Execution killed with signal 9
6 Runtime error 339 ms 131072 KB Execution killed with signal 9
7 Runtime error 328 ms 131072 KB Execution killed with signal 9
8 Runtime error 289 ms 131072 KB Execution killed with signal 9
9 Runtime error 769 ms 131072 KB Execution killed with signal 9
10 Runtime error 329 ms 131072 KB Execution killed with signal 9
11 Runtime error 329 ms 131072 KB Execution killed with signal 9
12 Runtime error 336 ms 131072 KB Execution killed with signal 9
13 Runtime error 583 ms 131072 KB Execution killed with signal 9
14 Correct 113 ms 20308 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 492 ms 131072 KB Execution killed with signal 9
2 Runtime error 341 ms 131072 KB Execution killed with signal 9
3 Correct 79 ms 24916 KB Output is correct
4 Runtime error 507 ms 131072 KB Execution killed with signal 9
5 Runtime error 332 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1036 ms 34868 KB Time limit exceeded
7 Runtime error 345 ms 131072 KB Execution killed with signal 9
8 Correct 79 ms 24916 KB Output is correct
9 Correct 69 ms 17104 KB Output is correct