oj.uz

Submission #870177

# Submission time Handle Problem Language Result Execution time Memory
870177 2023-11-07T07:02:49 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 142 ms 23764 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 15, L = 2e0 + 20;
int n, q, r, par[N][L], lst[N], st[N], ft[N], dfa[N], num[N];
bool ext[4 * N], mark[N];
vector<int> adj[N];

bool cmp(const int &a, const int &b) {
	return lst[a] < lst[b];
}

void dfs1(int v, int p) {
	lst[v] = v;
	for (int u: adj[v]) {
		dfs1(u, v);
		lst[v] = min(lst[v], lst[u]);
	}
}

void dfs2(int v, int p) {
	static int time = 0;
	dfa[time] = v;
	st[v] = time++;
	for (int u: adj[v])
		if (u != p)
			dfs2(u, v);
	ft[v] = time;
}

void make_tree(int l, int r, int t) {
	if (r - l == 1) {
		ext[t] = (st[dfa[l]] == ft[dfa[l]] - 1);
		return;
	}

	int k = (r + l + 1) / 2;
	make_tree(l, k, 2 * t);
	make_tree(k, r, 2 * t + 1);
	ext[t] = (ext[2 * t] | ext[2 * t + 1]);
}

int find_place(int l, int r, int t) {
	if (r - l == 1) 
		return dfa[l];

	int k = (r + l + 1) / 2;
	if (ext[2 * t])
		return find_place(l, k, 2 * t);
	else
		return find_place(k, r, 2 * t + 1);
}

void update(int p, bool x, int l, int r, int t) {
	if (r - l == 1) {
		ext[t] = x;
		return;
	}

	int k = (r + l + 1) / 2;
	if (p < k)
		update(p, x, l, k, 2 * t);
	else
		update(p, x, k, r, 2 * t + 1);
	ext[t] = (ext[2 * t] | ext[2 * t + 1]);
}

void read_input() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> par[i][0];
		if (par[i][0] != 0)
			adj[par[i][0]].push_back(i);
		else
			r = i;
	}
}

void solve() {
	memset(lst, 63, sizeof lst);
	dfs1(r, 0);
	for (int i = 1; i <= n; i++) 
		sort(adj[i].begin(), adj[i].end(), cmp);
	dfs2(r, 0);
	make_tree(0, n, 1);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++)
			par[j][i] = par[par[j][i - 1]][i - 1];

	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int k;
			cin >> k;
			for (int i = 0; i < k; i++) {
				int v = find_place(0, n, 1);
				update(st[v], false, 0, n, 1);
				mark[v] = true;
				num[par[v][0]]++;
				if (num[par[v][0]] == adj[par[v][0]].size()) 
					update(st[par[v][0]], true, 0, n, 1);
				if (i == k - 1)
					cout << v << '\n';
			}
		}
		else {
			int x;
			cin >> x;

			int p = x, res = 0;
			for (int i = L - 1; i >= 0; i--)
				if (mark[par[p][i]]) {
					p = par[p][i];
					res += (1 << i);
				}
			cout << res << '\n';
			
			mark[p] = false;
			num[par[p][0]]--;
			if (num[p] == adj[p].size()) {
				update(st[p], true, 0, n, 1);
				update(st[par[p][0]], false, 0, n, 1);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return cout << '\n', 0;
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     if (num[par[v][0]] == adj[par[v][0]].size())
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:121:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    if (num[p] == adj[p].size()) {
      |        ~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 93 ms 13968 KB Output is correct
3 Correct 40 ms 14172 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 6 ms 6848 KB Output is correct
10 Correct 17 ms 7048 KB Output is correct
11 Correct 86 ms 14112 KB Output is correct
12 Correct 40 ms 14184 KB Output is correct
13 Correct 75 ms 14108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10668 KB Output is correct
2 Correct 98 ms 19060 KB Output is correct
3 Correct 53 ms 15308 KB Output is correct
4 Correct 55 ms 10616 KB Output is correct
5 Correct 54 ms 10328 KB Output is correct
6 Correct 58 ms 10328 KB Output is correct
7 Correct 73 ms 9816 KB Output is correct
8 Correct 32 ms 10588 KB Output is correct
9 Correct 91 ms 19540 KB Output is correct
10 Correct 102 ms 18952 KB Output is correct
11 Correct 86 ms 19036 KB Output is correct
12 Correct 95 ms 17188 KB Output is correct
13 Correct 61 ms 21480 KB Output is correct
14 Correct 50 ms 15204 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13760 KB Output is correct
2 Correct 100 ms 17480 KB Output is correct
3 Correct 79 ms 20688 KB Output is correct
4 Correct 62 ms 17488 KB Output is correct
5 Correct 66 ms 16988 KB Output is correct
6 Correct 66 ms 17196 KB Output is correct
7 Correct 68 ms 15708 KB Output is correct
8 Correct 69 ms 20696 KB Output is correct
9 Correct 101 ms 19536 KB Output is correct
10 Correct 99 ms 19284 KB Output is correct
11 Correct 98 ms 19280 KB Output is correct
12 Correct 111 ms 17492 KB Output is correct
13 Correct 142 ms 23636 KB Output is correct
14 Correct 87 ms 15376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19640 KB Output is correct
2 Correct 103 ms 17488 KB Output is correct
3 Correct 67 ms 23380 KB Output is correct
4 Correct 129 ms 19576 KB Output is correct
5 Correct 115 ms 19164 KB Output is correct
6 Correct 94 ms 19028 KB Output is correct
7 Correct 110 ms 17648 KB Output is correct
8 Correct 64 ms 23764 KB Output is correct
9 Correct 66 ms 15384 KB Output is correct