oj.uz

Submission #872079

# Submission time Handle Problem Language Result Execution time Memory
872079 2023-11-12T09:23:26 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];
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 > it[v] + 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 > it[v] + 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:95:20: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |  cout << h[v] - h[p] << '\n';
      |                 ~~~^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 185 ms 31792 KB Output is correct
3 Correct 52 ms 14308 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 10 ms 9052 KB Output is correct
8 Correct 4 ms 9036 KB Output is correct
9 Correct 10 ms 10252 KB Output is correct
10 Correct 42 ms 15292 KB Output is correct
11 Correct 189 ms 31568 KB Output is correct
12 Correct 52 ms 14424 KB Output is correct
13 Correct 501 ms 16288 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12120 KB Output is correct
2 Runtime error 340 ms 131072 KB Execution killed with signal 9
3 Correct 67 ms 16844 KB Output is correct
4 Runtime error 651 ms 131072 KB Execution killed with signal 9
5 Runtime error 493 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1073 ms 48464 KB Time limit exceeded
7 Runtime error 787 ms 131072 KB Execution killed with signal 9
8 Correct 27 ms 12124 KB Output is correct
9 Execution timed out 1050 ms 94884 KB Time limit exceeded
10 Runtime error 358 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1072 ms 113340 KB Time limit exceeded
12 Runtime error 703 ms 131072 KB Execution killed with signal 9
13 Correct 79 ms 24400 KB Output is correct
14 Correct 71 ms 17148 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 443 ms 131072 KB Execution killed with signal 9
2 Runtime error 371 ms 131072 KB Execution killed with signal 9
3 Runtime error 306 ms 131072 KB Execution killed with signal 9
4 Runtime error 320 ms 131072 KB Execution killed with signal 9
5 Runtime error 342 ms 131072 KB Execution killed with signal 9
6 Runtime error 344 ms 131072 KB Execution killed with signal 9
7 Runtime error 363 ms 131072 KB Execution killed with signal 9
8 Runtime error 303 ms 131072 KB Execution killed with signal 9
9 Runtime error 757 ms 131072 KB Execution killed with signal 9
10 Runtime error 353 ms 131072 KB Execution killed with signal 9
11 Runtime error 353 ms 131072 KB Execution killed with signal 9
12 Runtime error 348 ms 131072 KB Execution killed with signal 9
13 Runtime error 620 ms 131072 KB Execution killed with signal 9
14 Correct 127 ms 20092 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 126256 KB Time limit exceeded
2 Runtime error 360 ms 131072 KB Execution killed with signal 9
3 Correct 83 ms 26448 KB Output is correct
4 Execution timed out 1066 ms 119476 KB Time limit exceeded
5 Runtime error 351 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1045 ms 34640 KB Time limit exceeded
7 Runtime error 376 ms 131072 KB Execution killed with signal 9
8 Correct 84 ms 26448 KB Output is correct
9 Correct 70 ms 16844 KB Output is correct