Submission #110690

#	Time	Username	Problem	Language	Result	Execution time	Memory
110690		ckodser	Ball Machine (BOI13_ballmachine)	C++14	0.56 / 100	1077 ms	130172 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, ts, P[N], H[N], rev[N], st[N], fn[N], mn[N];
vector < int > Adj[N];
set < int > S;
struct CMPH {
	inline bool operator () (int v, int u) {
		return (H[v] > H[u]);
	}
};
set < int , CMPH > T[N * 2];
bool CMP(int i, int j)
{
	return (mn[i] < mn[j]);
}
bool CMP2(int i, int j)
{
	return (st[i] < st[j]);
}
void DFS(int v)
{
	mn[v] = v;
	st[v] = ts ++;
	for (int &u : Adj[v])
	{
		H[u] = H[v] + 1;
		DFS(u);
		mn[v] = min(mn[v], mn[u]);
	}
	fn[v] = ts;
}
void DFS2(int v)
{
	for (int &u : Adj[v])
		DFS2(u);
	P[v] = ts ++;
	rev[P[v]] = v;
	S.insert(P[v]);
}
inline void Add(int le, int ri, int v)
{
	le += n + 1;
	ri += n + 1;
	for (; le < ri; le >>= 1, ri >>= 1)
	{
		if (le & 1) T[le].insert(v), le ++;
		if (ri & 1) ri --, T[ri].insert(v);
	}
}
inline void Del(int le, int ri, int v)
{
	le += n + 1;
	ri += n + 1;
	for (; le < ri; le >>= 1, ri >>= 1)
	{
		if (le & 1) T[le].erase(v), le ++;
		if (ri & 1) ri --, T[ri].erase(v);
	}
}
inline int Get(int i)
{
	int v = 0;
	i += n + 1;
	for (; i; i >>= 1)
		if (H[v] < H[*T[i].begin()])
			v = *T[i].begin();
	return (v);
}
int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1, p; i <= n; i++)
		scanf("%d", &p), Adj[p].push_back(i);
	DFS(0);
	for (int i = 0; i <= n; i++)
		sort(Adj[i].begin(), Adj[i].end(), CMP);
	ts = 0; DFS2(0);
	for (int i = 0; i <= n; i++)
		Add(st[i], fn[i], i);
	for (int i = 0; i <= n; i++)
		sort(Adj[i].begin(), Adj[i].end(), CMP2);
	for (; q; q --)
	{
		int tp, v;
		scanf("%d%d", &tp, &v);
		if (tp == 1)
		{
			int u;
			for (; v; v --)
			{
				u = rev[*S.begin()];
				S.erase(S.begin());
				Del(st[u], fn[u], u);
			}
			printf("%d\n", u);
		}
		else
		{
			int u = Get(st[v]);
			int lb = upper_bound(Adj[u].begin(), Adj[u].end(), st[v], CMP2) - Adj[u].begin() - 1;
			u = Adj[u][lb];
			S.insert(P[u]);
			Add(st[u], fn[u], u);
			printf("%d\n", H[v] - H[u]);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p), Adj[p].push_back(i);
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tp, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0.5555555555555556 / 5