oj.uz

Submission #872216

# Submission time Handle Problem Language Result Execution time Memory
872216 2023-11-12T14:15:20 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 > -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 > 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 (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 (sq[i / SQ].empty() && one[i].empty()) 
		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);
	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:98:20: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |  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 177 ms 31920 KB Output is correct
3 Correct 51 ms 14316 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9104 KB Output is correct
7 Correct 10 ms 9048 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 11 ms 10308 KB Output is correct
10 Correct 34 ms 14684 KB Output is correct
11 Correct 174 ms 31224 KB Output is correct
12 Correct 52 ms 14416 KB Output is correct
13 Correct 497 ms 16356 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12120 KB Output is correct
2 Runtime error 342 ms 131072 KB Execution killed with signal 9
3 Correct 61 ms 17056 KB Output is correct
4 Runtime error 679 ms 131072 KB Execution killed with signal 9
5 Runtime error 489 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1076 ms 48288 KB Time limit exceeded
7 Runtime error 770 ms 131072 KB Execution killed with signal 9
8 Correct 27 ms 12120 KB Output is correct
9 Execution timed out 1034 ms 92240 KB Time limit exceeded
10 Runtime error 343 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1082 ms 113340 KB Time limit exceeded
12 Runtime error 701 ms 131072 KB Execution killed with signal 9
13 Correct 73 ms 24404 KB Output is correct
14 Correct 68 ms 16896 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 429 ms 131072 KB Execution killed with signal 9
2 Runtime error 351 ms 131072 KB Execution killed with signal 9
3 Runtime error 294 ms 131072 KB Execution killed with signal 9
4 Runtime error 317 ms 131072 KB Execution killed with signal 9
5 Runtime error 332 ms 131072 KB Execution killed with signal 9
6 Runtime error 347 ms 131072 KB Execution killed with signal 9
7 Runtime error 347 ms 131072 KB Execution killed with signal 9
8 Runtime error 305 ms 131072 KB Execution killed with signal 9
9 Runtime error 765 ms 131072 KB Execution killed with signal 9
10 Runtime error 361 ms 131072 KB Execution killed with signal 9
11 Runtime error 341 ms 131072 KB Execution killed with signal 9
12 Runtime error 347 ms 131072 KB Execution killed with signal 9
13 Runtime error 583 ms 131072 KB Execution killed with signal 9
14 Correct 128 ms 20024 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 113484 KB Time limit exceeded
2 Runtime error 360 ms 131072 KB Execution killed with signal 9
3 Correct 89 ms 26480 KB Output is correct
4 Execution timed out 1070 ms 116408 KB Time limit exceeded
5 Runtime error 338 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1029 ms 34692 KB Time limit exceeded
7 Runtime error 356 ms 131072 KB Execution killed with signal 9
8 Correct 86 ms 26468 KB Output is correct
9 Correct 61 ms 16752 KB Output is correct