oj.uz

Submission #282991

# Submission time Handle Problem Language Result Execution time Memory
282991 2020-08-25T08:20:08 Z usuyus Ball Machine (BOI13_ballmachine) C++14
100 / 100
 630 ms 31260 KB 
#include <bits/stdc++.h>
#define N 100001
#define L 21
using namespace std;

int n, q, root, lg[N];
int par[N][L], mn[N], revord[N];
vector<int> tree[N], ord;

struct comp {
	bool operator() (int x, int y) const {
		return revord[x] < revord[y];
	}
};

set<int, comp> st;
bool vis[N];

int min_dfs(int node) {
	int res = node;
	for (int child : tree[node]) {
		res = min(res, min_dfs(child));
	}
	return mn[node] = res;
}

void ord_dfs(int node) {
	vector<pair<int, int>> w;
	for (int child : tree[node]) {
		w.push_back(make_pair(mn[child], child));
	}
	sort(w.begin(), w.end());
	for (auto child : w) ord_dfs(child.second);
	ord.push_back(node);
	revord[node] = ord.size()-1;
}

void fill_par() {
	for (int l=1; l<L; l++) {
		for (int i=1; i<=n; i++) {
			par[i][l] = par[par[i][l-1]][l-1];
		}
	}
}

int main() {
	cin>>n>>q; lg[0] = -1;
	for (int i=1; i<=n; i++) {
		int p; cin>>p;
		if (p == 0) root = i;
		tree[p].push_back(i);
		par[i][0] = p;
		lg[i] = lg[i/2] + 1;
	}

	min_dfs(root);
	ord_dfs(root);
	fill_par();

	for (int i=1; i<=n; i++) st.insert(i);

	while (q--) {
		int t; cin>>t;
		if (t == 1) {
			int k; cin>>k;
			while (k--) {
				int x = *st.begin();
				vis[x] = 1;
				if (k == 0) cout<<x<<endl;
				st.erase(st.begin());
			}
		} else {
			int x; cin>>x;
			int y = x, len = 0;

			for (int l=L-1; l>=0; l--) {
				if (vis[par[y][l]]) y = par[y][l], len += 1<<l;
			}

			vis[y] = 0;
			st.insert(y);
			cout<<len<<endl;
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 489 ms 14584 KB Output is correct
3 Correct 408 ms 14712 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 34 ms 3456 KB Output is correct
10 Correct 96 ms 5632 KB Output is correct
11 Correct 495 ms 14620 KB Output is correct
12 Correct 407 ms 14712 KB Output is correct
13 Correct 469 ms 14584 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 8440 KB Output is correct
2 Correct 592 ms 25580 KB Output is correct
3 Correct 443 ms 19652 KB Output is correct
4 Correct 353 ms 10072 KB Output is correct
5 Correct 373 ms 10208 KB Output is correct
6 Correct 403 ms 9956 KB Output is correct
7 Correct 347 ms 8888 KB Output is correct
8 Correct 270 ms 8440 KB Output is correct
9 Correct 562 ms 26076 KB Output is correct
10 Correct 584 ms 25892 KB Output is correct
11 Correct 549 ms 25892 KB Output is correct
12 Correct 585 ms 22964 KB Output is correct
13 Correct 489 ms 28276 KB Output is correct
14 Correct 434 ms 19560 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 14372 KB Output is correct
2 Correct 621 ms 22720 KB Output is correct
3 Correct 406 ms 25720 KB Output is correct
4 Correct 408 ms 21232 KB Output is correct
5 Correct 398 ms 21052 KB Output is correct
6 Correct 404 ms 20900 KB Output is correct
7 Correct 413 ms 18992 KB Output is correct
8 Correct 403 ms 25720 KB Output is correct
9 Correct 630 ms 25700 KB Output is correct
10 Correct 586 ms 25248 KB Output is correct
11 Correct 621 ms 25256 KB Output is correct
12 Correct 626 ms 22884 KB Output is correct
13 Correct 607 ms 31260 KB Output is correct
14 Correct 536 ms 19688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 25788 KB Output is correct
2 Correct 609 ms 22980 KB Output is correct
3 Correct 524 ms 31220 KB Output is correct
4 Correct 606 ms 25824 KB Output is correct
5 Correct 605 ms 25248 KB Output is correct
6 Correct 562 ms 25348 KB Output is correct
7 Correct 603 ms 23108 KB Output is correct
8 Correct 506 ms 31092 KB Output is correct
9 Correct 447 ms 19688 KB Output is correct