Submission #110692

#	Time	Username	Problem	Language	Result	Execution time	Memory
110692		ckodser	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	403 ms	25436 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
const int N = 100005, LG = 18;
int n, q, ts, P[N], H[N], rev[N], mn[N], par[N][LG], M[N];
vector < int > Adj[N];
set < int > S;
bool CMP(int i, int j)
{
	return (mn[i] < mn[j]);
}
void DFS(int v)
{
	mn[v] = v;
	for (int i = 1; i < LG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (int &u : Adj[v])
	{
		H[u] = H[v] + 1;
		par[u][0] = v;
		DFS(u);
		mn[v] = min(mn[v], mn[u]);
	}
}
void DFS2(int v)
{
	for (int &u : Adj[v])
		DFS2(u);
	P[v] = ts ++;
	rev[P[v]] = v;
	S.insert(P[v]);
}
inline int Get(int v)
{
	for (int i = LG - 1; ~ i; i --)
		if (M[par[v][i]])
			v = par[v][i];
	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);
	DFS2(0);
	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());
				M[u] = 1;
			}
			printf("%d\n", u);
		}
		else
		{
			int u = Get(v);
			M[u] = 0;
			S.insert(P[u]);
			printf("%d\n", H[v] - H[u]);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:41: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:43: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:51: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: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5