Submission #870165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870165	2023-11-07T06:43:45 Z	vjudge1	Ball Machine (BOI13_ballmachine)	C++17	50.0549 / 100	117 ms	25356 KB

ballmachine

#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])
		if (u != p) {
			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 = 0; i < n; i++) {
		cin >> par[i + 1][0];
		if (par[i + 1][0] != 0)
			adj[par[i + 1][0]].push_back(i + 1);
		else
			r = i + 1;
	}
}

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 { // update mark, ext, num
			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]]--;
			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:102:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if (num[par[v][0]] == adj[par[v][0]].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	77 ms	14000 KB	Output isn't correct
3	Correct	38 ms	14164 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	6748 KB	Output is correct
7	Incorrect	2 ms	6748 KB	Output isn't correct
8	Incorrect	2 ms	6748 KB	Output isn't correct
9	Incorrect	5 ms	6856 KB	Output isn't correct
10	Incorrect	15 ms	7060 KB	Output isn't correct
11	Incorrect	105 ms	13916 KB	Output isn't correct
12	Correct	40 ms	14348 KB	Output is correct
13	Incorrect	63 ms	14004 KB	Output isn't correct

Subtask #2

4.28571428571 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	11136 KB	Output isn't correct
2	Incorrect	105 ms	19792 KB	Output isn't correct
3	Correct	49 ms	15212 KB	Output is correct
4	Incorrect	57 ms	10880 KB	Output isn't correct
5	Incorrect	49 ms	10804 KB	Output isn't correct
6	Incorrect	44 ms	10832 KB	Output isn't correct
7	Incorrect	58 ms	10080 KB	Output isn't correct
8	Incorrect	26 ms	11096 KB	Output isn't correct
9	Incorrect	84 ms	20308 KB	Output isn't correct
10	Incorrect	117 ms	19796 KB	Output isn't correct
11	Incorrect	112 ms	19996 KB	Output isn't correct
12	Incorrect	88 ms	17500 KB	Output isn't correct
13	Incorrect	61 ms	22864 KB	Output isn't correct
14	Correct	45 ms	15308 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	14160 KB	Output is correct
2	Correct	92 ms	18092 KB	Output is correct
3	Correct	66 ms	21844 KB	Output is correct
4	Correct	57 ms	18000 KB	Output is correct
5	Correct	59 ms	17744 KB	Output is correct
6	Correct	56 ms	17624 KB	Output is correct
7	Correct	56 ms	16212 KB	Output is correct
8	Correct	64 ms	21840 KB	Output is correct
9	Correct	92 ms	20456 KB	Output is correct
10	Correct	105 ms	20048 KB	Output is correct
11	Correct	103 ms	19984 KB	Output is correct
12	Correct	98 ms	18000 KB	Output is correct
13	Correct	103 ms	25356 KB	Output is correct
14	Correct	99 ms	15220 KB	Output is correct

Subtask #4

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	101 ms	20536 KB	Output isn't correct
2	Incorrect	86 ms	17944 KB	Output isn't correct
3	Incorrect	65 ms	25168 KB	Output isn't correct
4	Incorrect	102 ms	20328 KB	Output isn't correct
5	Incorrect	87 ms	19912 KB	Output isn't correct
6	Incorrect	81 ms	20036 KB	Output isn't correct
7	Incorrect	98 ms	18108 KB	Output isn't correct
8	Incorrect	71 ms	25172 KB	Output isn't correct
9	Incorrect	54 ms	15568 KB	Output isn't correct