oj.uz

Submission #66126

# Submission time Handle Problem Language Result Execution time Memory
66126 2018-08-09T17:58:56 Z MatheusLealV Ball Machine (BOI13_ballmachine) C++17
0 / 100
 921 ms 79620 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];

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;

void build1(int nod, int a, int b)
{
	if(a == b)
	{
		tree1[nod] = a;

		return;
	}

	build1(ll, a, mid), build1(rr, mid + 1, b);

	if(v[tree1[ll]] < v[tree1[rr]]) tree1[nod] = tree1[ll];

	else tree1[nod] = tree1[rr];
}

int query1(int nod, int a, int b, int i, int j)
{
	if(j < a or i > b) return 0;

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

	int A = query1(ll, a, mid, i, j), B = query1(rr, mid + 1, b, i, j);

	return (v[A] < v[B] ? A: B);
}

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

	ini[x] = ++cnt;

	v[cnt] = x;

	anc[x][0] = p;

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

		dfs(v, x);
	}

	fim[x] = cnt;
}

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

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

		order.push_back({query1(1, 1, n, ini[v], fim[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);

	build1(1, 1, n);

	solve(root, root);

	Tree.init();

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

		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, anc[x][j], anc[x][j]);

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

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

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 13688 KB Output isn't correct
2 Incorrect 480 ms 18664 KB Output isn't correct
3 Incorrect 238 ms 19688 KB Output isn't correct
4 Incorrect 14 ms 19688 KB Output isn't correct
5 Incorrect 13 ms 19688 KB Output isn't correct
6 Incorrect 16 ms 19688 KB Output isn't correct
7 Incorrect 14 ms 19688 KB Output isn't correct
8 Incorrect 16 ms 19688 KB Output isn't correct
9 Incorrect 42 ms 19688 KB Output isn't correct
10 Incorrect 112 ms 19688 KB Output isn't correct
11 Incorrect 510 ms 21360 KB Output isn't correct
12 Incorrect 273 ms 22412 KB Output isn't correct
13 Incorrect 502 ms 23680 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 24260 KB Output isn't correct
2 Incorrect 906 ms 34560 KB Output isn't correct
3 Incorrect 326 ms 34560 KB Output isn't correct
4 Incorrect 395 ms 34560 KB Output isn't correct
5 Incorrect 388 ms 34560 KB Output isn't correct
6 Incorrect 503 ms 34560 KB Output isn't correct
7 Incorrect 434 ms 34560 KB Output isn't correct
8 Incorrect 143 ms 34560 KB Output isn't correct
9 Incorrect 749 ms 39924 KB Output isn't correct
10 Incorrect 921 ms 41980 KB Output isn't correct
11 Incorrect 905 ms 43428 KB Output isn't correct
12 Incorrect 767 ms 43428 KB Output isn't correct
13 Incorrect 313 ms 50164 KB Output isn't correct
14 Incorrect 279 ms 50164 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 50164 KB Output isn't correct
2 Incorrect 773 ms 50164 KB Output isn't correct
3 Incorrect 594 ms 52396 KB Output isn't correct
4 Incorrect 537 ms 52396 KB Output isn't correct
5 Incorrect 500 ms 52396 KB Output isn't correct
6 Incorrect 510 ms 52396 KB Output isn't correct
7 Incorrect 477 ms 52396 KB Output isn't correct
8 Incorrect 495 ms 56956 KB Output isn't correct
9 Incorrect 675 ms 56956 KB Output isn't correct
10 Incorrect 841 ms 56956 KB Output isn't correct
11 Incorrect 768 ms 58252 KB Output isn't correct
12 Incorrect 829 ms 58252 KB Output isn't correct
13 Incorrect 880 ms 67964 KB Output isn't correct
14 Incorrect 442 ms 67964 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 727 ms 67964 KB Output isn't correct
2 Incorrect 915 ms 67964 KB Output isn't correct
3 Incorrect 369 ms 73060 KB Output isn't correct
4 Incorrect 896 ms 73060 KB Output isn't correct
5 Incorrect 825 ms 73060 KB Output isn't correct
6 Incorrect 739 ms 73060 KB Output isn't correct
7 Incorrect 763 ms 73060 KB Output isn't correct
8 Incorrect 377 ms 79620 KB Output isn't correct
9 Incorrect 271 ms 79620 KB Output isn't correct