제출 #66127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66127		MatheusLealV	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	983 ms	33568 KiB

ballmachine

#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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5