oj.uz

Submission #870175

# Submission time Handle Problem Language Result Execution time Memory
870175 2023-11-07T06:58:09 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
50.0549 / 100
 109 ms 23632 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);
		}
	}
}

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
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6748 KB Output isn't correct
2 Incorrect 78 ms 14096 KB Output isn't correct
3 Correct 37 ms 14160 KB Output is correct
4 Incorrect 1 ms 6744 KB Output isn't correct
5 Incorrect 1 ms 6748 KB Output isn't correct
6 Correct 1 ms 7000 KB Output is correct
7 Incorrect 2 ms 6744 KB Output isn't correct
8 Incorrect 2 ms 6748 KB Output isn't correct
9 Incorrect 5 ms 6860 KB Output isn't correct
10 Incorrect 15 ms 7004 KB Output isn't correct
11 Incorrect 62 ms 13968 KB Output isn't correct
12 Correct 38 ms 14120 KB Output is correct
13 Incorrect 60 ms 14168 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 10832 KB Output isn't correct
2 Incorrect 82 ms 18948 KB Output isn't correct
3 Correct 50 ms 15500 KB Output is correct
4 Incorrect 44 ms 10584 KB Output isn't correct
5 Incorrect 50 ms 10332 KB Output isn't correct
6 Incorrect 38 ms 10332 KB Output isn't correct
7 Incorrect 41 ms 9880 KB Output isn't correct
8 Incorrect 26 ms 10844 KB Output isn't correct
9 Incorrect 77 ms 19432 KB Output isn't correct
10 Incorrect 98 ms 19064 KB Output isn't correct
11 Incorrect 80 ms 19092 KB Output isn't correct
12 Incorrect 76 ms 17104 KB Output isn't correct
13 Incorrect 60 ms 21588 KB Output isn't correct
14 Correct 49 ms 15312 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13888 KB Output is correct
2 Correct 88 ms 17492 KB Output is correct
3 Correct 66 ms 20564 KB Output is correct
4 Correct 61 ms 17396 KB Output is correct
5 Correct 56 ms 16988 KB Output is correct
6 Correct 67 ms 16988 KB Output is correct
7 Correct 59 ms 15708 KB Output is correct
8 Correct 64 ms 20688 KB Output is correct
9 Correct 90 ms 19540 KB Output is correct
10 Correct 93 ms 19176 KB Output is correct
11 Correct 91 ms 19196 KB Output is correct
12 Correct 90 ms 17488 KB Output is correct
13 Correct 102 ms 23632 KB Output is correct
14 Correct 77 ms 15312 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 19864 KB Output isn't correct
2 Incorrect 87 ms 17624 KB Output isn't correct
3 Incorrect 64 ms 23380 KB Output isn't correct
4 Incorrect 98 ms 19540 KB Output isn't correct
5 Incorrect 85 ms 19248 KB Output isn't correct
6 Incorrect 72 ms 19164 KB Output isn't correct
7 Incorrect 88 ms 17492 KB Output isn't correct
8 Incorrect 68 ms 23496 KB Output isn't correct
9 Incorrect 47 ms 15316 KB Output isn't correct