oj.uz

답안 #872748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872748 2023-11-13T16:32:38 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
94.2857 / 100
 1000 ms 44480 KB 
#include<bits/stdc++.h>
using namespace std;
 
#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 = 2e5 + 12, M = 20, SQ = 200;
vector<int> g[N];
int n, q, t, f[N], p[N], par[M][N], root, d[N], h[N], sum[N];
bool dp[N], a[N];

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[r] + 1 << '\n';
			add(r);
		}
		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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 853 ms 27480 KB Output is correct
3 Correct 460 ms 27432 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 4 ms 24924 KB Output is correct
6 Correct 5 ms 24924 KB Output is correct
7 Correct 7 ms 24920 KB Output is correct
8 Correct 6 ms 24924 KB Output is correct
9 Correct 31 ms 25084 KB Output is correct
10 Correct 163 ms 25464 KB Output is correct
11 Correct 939 ms 27268 KB Output is correct
12 Correct 446 ms 27740 KB Output is correct
13 Correct 836 ms 27408 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 28500 KB Output is correct
2 Correct 798 ms 36260 KB Output is correct
3 Correct 554 ms 28380 KB Output is correct
4 Correct 529 ms 28404 KB Output is correct
5 Correct 409 ms 28520 KB Output is correct
6 Correct 375 ms 28504 KB Output is correct
7 Correct 340 ms 27428 KB Output is correct
8 Correct 152 ms 28500 KB Output is correct
9 Correct 852 ms 36192 KB Output is correct
10 Correct 790 ms 36296 KB Output is correct
11 Correct 680 ms 36432 KB Output is correct
12 Correct 693 ms 31904 KB Output is correct
13 Correct 313 ms 41856 KB Output is correct
14 Correct 551 ms 28548 KB Output is correct

Subtask #3
34.2857142857 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 30544 KB Output is correct
2 Correct 985 ms 32468 KB Output is correct
3 Correct 409 ms 40228 KB Output is correct
4 Correct 452 ms 33872 KB Output is correct
5 Correct 472 ms 34088 KB Output is correct
6 Correct 430 ms 34056 KB Output is correct
7 Correct 406 ms 30800 KB Output is correct
8 Correct 430 ms 40316 KB Output is correct
9 Execution timed out 1043 ms 36176 KB Time limit exceeded
10 Correct 950 ms 36788 KB Output is correct
11 Correct 970 ms 36480 KB Output is correct
12 Correct 927 ms 32496 KB Output is correct
13 Correct 910 ms 44480 KB Output is correct
14 Execution timed out 1053 ms 27284 KB Time limit exceeded

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 874 ms 34996 KB Output is correct
2 Correct 862 ms 32580 KB Output is correct
3 Correct 339 ms 43880 KB Output is correct
4 Correct 797 ms 35020 KB Output is correct
5 Correct 805 ms 36416 KB Output is correct
6 Correct 648 ms 36276 KB Output is correct
7 Correct 847 ms 32480 KB Output is correct
8 Correct 345 ms 44028 KB Output is correct
9 Correct 691 ms 28360 KB Output is correct