oj.uz

답안 #96868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96868 2019-02-12T14:21:51 Z luciocf Ball Machine (BOI13_ballmachine) C++14
100 / 100
 628 ms 32504 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxl = 20;

int n, cont;
int menor[maxn], order[maxn], pos[maxn];
int tree[4*maxn], lazy[4*maxn];
int tab[maxn][maxl], nivel[maxn];

vector<int> grafo[maxn];

bool comp(int a, int b) {return menor[a] < menor[b];}

int dfs(int u, int p)
{
	menor[u] = u;
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		tab[v][0] = u, nivel[v] = nivel[u]+1;
		menor[u] = min(menor[u], dfs(v, u));
	}

	return menor[u];
}

void dfs2(int u, int p)
{
	vector<int> child;

	for (auto v: grafo[u])
		if (v != p) child.push_back(v);

	sort(child.begin(), child.end(), comp);

	for (auto v: child)
		dfs2(v, u);

	pos[u] = ++cont;
	order[cont] = u;
}

void flush(int node, int l, int r)
{
	if (lazy[node] == -1) return;

	if (l != r) lazy[2*node] = lazy[2*node+1] = lazy[node];

	tree[node] = (r-l+1)*lazy[node], lazy[node] = -1;
}

void upd(int node, int l, int r, int a, int b, int v)
{
	flush(node, l, r);

	if (l > b || r < a) return;

	if (l >= a && r <= b)
	{
		lazy[node] = v;
		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

	tree[node] = tree[2*node]+tree[2*node+1];
}

int query(int node, int l, int r, int pos)
{
	flush(node, l, r);

	if (l == r) return tree[node];

	int mid = (l+r)>>1;

	if (pos <= mid) return query(2*node, l, mid, pos);
	else return query(2*node+1, mid+1, r, pos);
}

int kth(int node, int l, int r, int k)
{
	flush(node, l, r);

	if (l == r) return l;

	int mid = (l+r)>>1;

	if (mid-l+1-tree[2*node] >= k) return kth(2*node, l, mid, k);
	return kth(2*node+1, mid+1, r, k-(mid-l+1-tree[2*node]));
}

void build(void)
{
	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			tab[i][j] = tab[tab[i][j-1]][j-1];
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	memset(lazy, -1, sizeof lazy);

	int q;
	cin >> n >> q;

	int root;
	for (int i = 1; i <= n; i++)
	{
		int p;
		cin >> p;

		if (!p) root = i;
		else grafo[i].push_back(p), grafo[p].push_back(i);
	}

	dfs(root, 0); dfs2(root, 0);

	build();

	while (q--)
	{
		int op;
		cin >> op;

		if (op == 1)
		{
			int k;
			cin >> k;

			int x = kth(1, 1, n, k);
			upd(1, 1, n, 1, x, 1);

			cout << order[x] << "\n";
		}
		else
		{
			int u;
			cin >> u;

			int x = u;
			for (int i = maxl-1; i >= 0; i--)
				if (tab[u][i] && query(1, 1, n, pos[tab[u][i]]) == 1)
					u = tab[u][i];

			upd(1, 1, n, pos[u], pos[u], 0);

			cout << nivel[x]-nivel[u] << "\n";
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:126:20: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root, 0); dfs2(root, 0);
                ~~~~^~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 227 ms 13176 KB Output is correct
3 Correct 149 ms 13000 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct
5 Correct 6 ms 4348 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 8 ms 4480 KB Output is correct
8 Correct 6 ms 4480 KB Output is correct
9 Correct 16 ms 4992 KB Output is correct
10 Correct 41 ms 6528 KB Output is correct
11 Correct 274 ms 13176 KB Output is correct
12 Correct 113 ms 12920 KB Output is correct
13 Correct 182 ms 12800 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 9464 KB Output is correct
2 Correct 514 ms 24764 KB Output is correct
3 Correct 173 ms 17328 KB Output is correct
4 Correct 185 ms 10668 KB Output is correct
5 Correct 234 ms 10588 KB Output is correct
6 Correct 208 ms 10364 KB Output is correct
7 Correct 170 ms 9080 KB Output is correct
8 Correct 82 ms 9592 KB Output is correct
9 Correct 325 ms 24692 KB Output is correct
10 Correct 414 ms 24696 KB Output is correct
11 Correct 367 ms 24184 KB Output is correct
12 Correct 448 ms 20728 KB Output is correct
13 Correct 231 ms 28320 KB Output is correct
14 Correct 254 ms 17328 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 14776 KB Output is correct
2 Correct 628 ms 21740 KB Output is correct
3 Correct 307 ms 26764 KB Output is correct
4 Correct 254 ms 21044 KB Output is correct
5 Correct 370 ms 21120 KB Output is correct
6 Correct 292 ms 21236 KB Output is correct
7 Correct 303 ms 18168 KB Output is correct
8 Correct 363 ms 26872 KB Output is correct
9 Correct 448 ms 25364 KB Output is correct
10 Correct 581 ms 25448 KB Output is correct
11 Correct 622 ms 25464 KB Output is correct
12 Correct 582 ms 21656 KB Output is correct
13 Correct 595 ms 32504 KB Output is correct
14 Correct 244 ms 18476 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 25012 KB Output is correct
2 Correct 431 ms 21480 KB Output is correct
3 Correct 278 ms 31352 KB Output is correct
4 Correct 529 ms 25120 KB Output is correct
5 Correct 597 ms 24952 KB Output is correct
6 Correct 443 ms 24396 KB Output is correct
7 Correct 550 ms 21464 KB Output is correct
8 Correct 247 ms 31240 KB Output is correct
9 Correct 178 ms 17460 KB Output is correct