oj.uz

답안 #872740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872740 2023-11-13T16:21:05 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 999 ms 39596 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
 
const int N = 1e5 + 12, M = 20, SQ = 320;
vector<int> g[N];
int n, q, t, f[N], p[N], par[M][N], root, d[N], h[N], sum[SQ];
bool dp[SQ], a[SQ * SQ + 12];

void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int u;
		cin >> u;
		u--;
		par[0][i] = u;
		if (u == -1)
			root = i;
		else {
			g[u].pb(i);
			g[i].pb(u);
		}
	}
	par[0][root] = root;
}
 
void dfs1(int u) {
	d[u] = u;
	for (auto i: g[u])
		if (i != par[0][u]) {
			h[i] = h[u] + 1;
			dfs1(i);
			d[u] = min(d[u], d[i]);
		}
}
 
void dfs2(int u) {
	vector<pii> tmp;
	for (auto i: g[u])
		if (i != par[0][u])
			tmp.pb({d[i], i});
	sort(all(tmp));
	for (auto i: tmp)
		dfs2(i.S);
	f[t] = u;
	p[u] = t;
	t++;
}
 
void pre() {
	dfs1(root);
	dfs2(root);
	for (int i = 1; i < M; i++)
		for (int j = 0; j < n; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
}

void add(int x) {
	for (int i = 0; (i + 1) * SQ - 1 < x; i++) {
		sum[i] = SQ;
		dp[i] = true;
	}
	if (!dp[x / SQ]) 
		for (int i = (x / SQ) * SQ; i <= x; i++)
			if (!a[i]) {
				a[i] = true;
				sum[x / SQ]++;
			}
}

void rem(int x) {
	if (dp[x / SQ]) {
		fill(a + x - x % SQ, a + x - x % SQ + SQ, 1);
		sum[x / SQ] = SQ - 1;
		dp[x / SQ] = false;
		a[x] = false;
	}
	else if (a[x]) {
		a[x] = false;
		sum[x / SQ]--;
	}
}

int ask(int x) {
	int res = 0;
	for (int i = 0; (i + 1) * SQ - 1 < x; i++)
		res += sum[i];
	if (dp[x / SQ]) 
		res += (x % SQ) + 1;
	else 
		for (int i = x - x % SQ; i <= x; i++)
			res += a[i];
	return res;
}
 
void query() {
	while (q--) {
		int u, v;
		cin >> u >> v;
		if (u == 1) {
			int l = -1, r = n;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (mid + 1 - ask(mid) <= v)
					l = mid;
				else
					r = mid;
			}
			cout << f[l] + 1 << '\n';
			add(l);
		}
		else {
			v--;
			int z = v;
			for (int i = M - 1; ~i; i--)
				if ((ask(p[par[i][v]]) - ask(p[par[i][v]] - 1)) > 0)
					v = par[i][v];
			cout << h[z] - h[v] << '\n';
			rem(p[v]);
		}
	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), pre(), query();
	return 0;
}

Subtask #1
19.2307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21340 KB Output is correct
2 Correct 848 ms 24712 KB Output is correct
3 Correct 428 ms 24664 KB Output is correct
4 Incorrect 3 ms 21336 KB Output isn't correct
5 Correct 4 ms 21508 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Incorrect 5 ms 21588 KB Output isn't correct
8 Correct 5 ms 21340 KB Output is correct
9 Correct 42 ms 21744 KB Output is correct
10 Correct 62 ms 22364 KB Output is correct
11 Correct 857 ms 24604 KB Output is correct
12 Correct 414 ms 24712 KB Output is correct
13 Incorrect 813 ms 24496 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 24916 KB Output is correct
2 Correct 691 ms 33536 KB Output is correct
3 Correct 483 ms 25656 KB Output is correct
4 Correct 437 ms 24876 KB Output is correct
5 Correct 373 ms 25248 KB Output is correct
6 Incorrect 359 ms 25240 KB Output isn't correct
7 Correct 362 ms 23992 KB Output is correct
8 Correct 117 ms 24896 KB Output is correct
9 Correct 728 ms 32440 KB Output is correct
10 Correct 692 ms 33340 KB Output is correct
11 Incorrect 538 ms 33024 KB Output isn't correct
12 Correct 675 ms 29008 KB Output is correct
13 Correct 271 ms 37144 KB Output is correct
14 Correct 463 ms 25436 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 283 ms 27196 KB Output is correct
2 Correct 828 ms 29908 KB Output is correct
3 Correct 357 ms 35664 KB Output is correct
4 Correct 490 ms 30292 KB Output is correct
5 Correct 373 ms 30804 KB Output is correct
6 Correct 378 ms 30880 KB Output is correct
7 Correct 363 ms 27732 KB Output is correct
8 Correct 353 ms 35580 KB Output is correct
9 Correct 894 ms 32548 KB Output is correct
10 Correct 818 ms 33420 KB Output is correct
11 Correct 785 ms 33108 KB Output is correct
12 Correct 805 ms 29632 KB Output is correct
13 Correct 756 ms 39596 KB Output is correct
14 Correct 999 ms 25716 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 707 ms 32592 KB Output is correct
2 Correct 722 ms 29868 KB Output is correct
3 Correct 260 ms 38996 KB Output is correct
4 Correct 673 ms 32840 KB Output is correct
5 Correct 697 ms 33460 KB Output is correct
6 Incorrect 547 ms 33148 KB Output isn't correct
7 Correct 705 ms 29448 KB Output is correct
8 Correct 267 ms 39100 KB Output is correct
9 Correct 455 ms 25584 KB Output is correct