Submission #206640

#	Time	Username	Problem	Language	Result	Execution time	Memory
206640		DodgeBallMan	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	243 ms	25068 KiB

ballmachine

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+100;

vector<int> g[N];
int n, q, root, dp[N], pos[N], dep[N];
int par[N][18], has[N];
priority_queue<pii, vector<pii>, greater<pii>> Q;

int dfs( int u, int p ) {
	dp[u] = u, par[u][0] = p;
	dep[u] = dep[p] + 1;
	for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1];
	for(int v : g[u]) if(v != p) dp[u] = min(dp[u], dfs(v, u));
	sort(g[u].begin(), g[u].end(), [&](const int &a, const int &b) {
		return dp[a] < dp[b];
	});
	return dp[u];
}

void get(int u, int p) {
	static int idx = 0;
	for(int v : g[u]) if( v != p ) get( v, u );
	pos[u] = ++idx;
}

int main()
{
	scanf("%d %d",&n,&q);
	for( int i = 1, p ; i <= n ; i++ ) {
		scanf("%d",&p);
		if( !p )root = i;
		else g[p].emplace_back( i ), g[i].emplace_back( p );
	}
	dfs( root, 0 );
	get( root, 0 );
	for(int i = 1; i <= n; i++) Q.emplace(pos[i], i);
	for(int i = 1; i <= q; i++) {
		int T, a;
		scanf("%d %d", &T, &a);
		if(T == 1) {
			int ret = -1;
			while(a--) {
				pii now = Q.top(); Q.pop();
				has[now.y] = true;
				ret = now.y;
			}
			printf("%d\n", ret);
		} 
		else {
			int x = a;
			for(int i = 17; ~i; i--) if(has[par[x][i]]) x = par[x][i];
			has[x] = false;
			Q.emplace(pos[x], x);
			printf("%d\n", dep[a] - dep[x]);
		}
	}

	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:35: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:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~
ballmachine.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &T, &a);
   ~~~~~^~~~~~~~~~~~~~~~~

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