oj.uz

Submission #66127

# Submission time Handle Problem Language Result Execution time Memory
66127 2018-08-09T18:24:33 Z MatheusLealV Ball Machine (BOI13_ballmachine) C++17
100 / 100
 983 ms 33568 KB 
#include <bits/stdc++.h>
#define logn 20
#define N 100050
#define ll (2*nod)
#define rr (2*nod + 1)
#define mid ((a + b)/2)
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, q, pai[N], root, ini[N], fim[N], tree1[4*N], v[N], cnt, id[N];

int anc[N][logn], idx[N], deep[N], pos[N];

vector<int> grafo[N], lista;

struct T
{
	int tree[4*N], lazy[4*N];

	inline void init()
	{
		 memset(tree, 0, sizeof tree);

		 memset(lazy, -1, sizeof lazy);
	}

	inline void prop(int nod, int a, int b)
	{
		if(lazy[nod] == -1) return;

		tree[nod] = (b - a + 1)*lazy[nod];

		if(a != b)
		{
			lazy[ll] = lazy[nod];

			lazy[rr] = lazy[nod];
		}

		lazy[nod] = -1;
	}

	void upd(int nod, int a, int b, int i, int j, int x)
	{
		prop(nod, a, b);

		if(j < a or i > b) return;

		if(i <= a and j >= b)
		{
			tree[nod] = (b - a + 1)*x;

			if(a != b)
			{
				lazy[ll] = x;

				lazy[rr] = x;
			}

			return;		
		}

		upd(ll, a, mid, i, j, x), upd(rr, mid + 1, b, i, j, x);

		tree[nod] = tree[ll] + tree[rr];
	}

	int query(int nod, int a, int b, int i, int j)
	{
		prop(nod, a, b);

		if(j < a or i > b) return 0;

		if(i <= a and j >= b) return tree[nod];

		return query(ll, a, mid, i, j) + query(rr, mid + 1, b, i, j);
	}

	int kth(int nod, int a, int b, int k)
	{
		if(a == b) return a;

		if(tree[ll] < k) return kth(rr, mid + 1, b, k - tree[ll]);

		return kth(ll, a, mid, k);
	}

} Tree;

int menor[N];

void dfs(int x, int p)
{
	deep[x] = deep[p] + 1;

	ini[x] = ++cnt;

	v[cnt] = x;

	anc[x][0] = p;

	menor[x] = x;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		dfs(v, x);

		menor[x] = min(menor[x], menor[v]);
	}

	fim[x] = cnt;
}

void solve(int x, int p)
{
	vector<pii> order;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		order.push_back({menor[v], v});
	}

	sort(order.begin(), order.end());

	for(auto v: order) solve(v.s, x);

	lista.push_back(x);
}

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

	cin>>n>>q;

	for(int i = 1; i <= n; i++)
	{
		cin>>pai[i];

		if(pai[i]) grafo[pai[i]].push_back(i);

		else root = i;
	}

	memset(anc, -1, sizeof anc);

	dfs(root, root);

	solve(root, root);

	Tree.init();

	for(int i = 1; i <= n; i++)
	{
		idx[i] = lista[i - 1];

		pos[lista[i - 1]] = i;

		Tree.upd(1, 1, n, i, i, 1);
	}

	for(int j = 1; j < logn; j++)
		for(int i = 1; i <= n; i++) anc[i][j] = anc[anc[i][j - 1]][j - 1];

	while(q--)
	{
		int tipo, x;

		cin>>tipo>>x;

		if(tipo == 1)
		{
			int k = Tree.kth(1, 1, n, x);

			Tree.upd(1, 1, n, 1, k, 0);

			cout<<idx[k]<<"\n";
		}

		else
		{
			int y = x;

			for(int j = logn - 1; j >= 0; j--)
			{
				if(anc[x][j] == -1) continue;

				int A = Tree.query(1, 1, n, pos[anc[x][j]], pos[anc[x][j]]);

				if(!A) x = anc[x][j];
			}

			cout<<deep[y] - deep[x]<<"\n";

			Tree.upd(1, 1, n, pos[x], pos[x], 1);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13688 KB Output is correct
2 Correct 578 ms 17748 KB Output is correct
3 Correct 283 ms 17748 KB Output is correct
4 Correct 13 ms 17748 KB Output is correct
5 Correct 13 ms 17748 KB Output is correct
6 Correct 14 ms 17748 KB Output is correct
7 Correct 17 ms 17748 KB Output is correct
8 Correct 16 ms 17748 KB Output is correct
9 Correct 50 ms 17748 KB Output is correct
10 Correct 105 ms 17748 KB Output is correct
11 Correct 575 ms 17820 KB Output is correct
12 Correct 300 ms 17928 KB Output is correct
13 Correct 529 ms 17928 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 17928 KB Output is correct
2 Correct 777 ms 26052 KB Output is correct
3 Correct 331 ms 26052 KB Output is correct
4 Correct 346 ms 26052 KB Output is correct
5 Correct 418 ms 26052 KB Output is correct
6 Correct 388 ms 26052 KB Output is correct
7 Correct 391 ms 26052 KB Output is correct
8 Correct 175 ms 26052 KB Output is correct
9 Correct 582 ms 26052 KB Output is correct
10 Correct 844 ms 26200 KB Output is correct
11 Correct 680 ms 26200 KB Output is correct
12 Correct 645 ms 26200 KB Output is correct
13 Correct 349 ms 30920 KB Output is correct
14 Correct 349 ms 30920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 30920 KB Output is correct
2 Correct 769 ms 30920 KB Output is correct
3 Correct 429 ms 30920 KB Output is correct
4 Correct 511 ms 30920 KB Output is correct
5 Correct 506 ms 30920 KB Output is correct
6 Correct 659 ms 30920 KB Output is correct
7 Correct 525 ms 30920 KB Output is correct
8 Correct 500 ms 30920 KB Output is correct
9 Correct 791 ms 30920 KB Output is correct
10 Correct 764 ms 30920 KB Output is correct
11 Correct 705 ms 30920 KB Output is correct
12 Correct 663 ms 30920 KB Output is correct
13 Correct 669 ms 33568 KB Output is correct
14 Correct 654 ms 33568 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 33568 KB Output is correct
2 Correct 708 ms 33568 KB Output is correct
3 Correct 400 ms 33568 KB Output is correct
4 Correct 696 ms 33568 KB Output is correct
5 Correct 983 ms 33568 KB Output is correct
6 Correct 697 ms 33568 KB Output is correct
7 Correct 814 ms 33568 KB Output is correct
8 Correct 334 ms 33568 KB Output is correct
9 Correct 318 ms 33568 KB Output is correct