oj.uz

Submission #206640

# Submission time Handle Problem Language Result Execution time Memory
206640 2020-03-04T10:12:25 Z DodgeBallMan Ball Machine (BOI13_ballmachine) C++14
100 / 100
 243 ms 25068 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 132 ms 12404 KB Output is correct
3 Correct 95 ms 12152 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 13 ms 3320 KB Output is correct
10 Correct 29 ms 5108 KB Output is correct
11 Correct 136 ms 12404 KB Output is correct
12 Correct 98 ms 12148 KB Output is correct
13 Correct 133 ms 12404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7284 KB Output is correct
2 Correct 215 ms 20844 KB Output is correct
3 Correct 112 ms 16364 KB Output is correct
4 Correct 79 ms 8692 KB Output is correct
5 Correct 81 ms 8692 KB Output is correct
6 Correct 80 ms 8692 KB Output is correct
7 Correct 79 ms 7800 KB Output is correct
8 Correct 54 ms 7412 KB Output is correct
9 Correct 186 ms 20840 KB Output is correct
10 Correct 215 ms 20840 KB Output is correct
11 Correct 198 ms 20848 KB Output is correct
12 Correct 201 ms 18540 KB Output is correct
13 Correct 142 ms 21996 KB Output is correct
14 Correct 110 ms 16360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11888 KB Output is correct
2 Correct 224 ms 19052 KB Output is correct
3 Correct 163 ms 20332 KB Output is correct
4 Correct 139 ms 17260 KB Output is correct
5 Correct 159 ms 17260 KB Output is correct
6 Correct 148 ms 17128 KB Output is correct
7 Correct 143 ms 15596 KB Output is correct
8 Correct 151 ms 20328 KB Output is correct
9 Correct 204 ms 21096 KB Output is correct
10 Correct 226 ms 20972 KB Output is correct
11 Correct 236 ms 20972 KB Output is correct
12 Correct 222 ms 19056 KB Output is correct
13 Correct 243 ms 25068 KB Output is correct
14 Correct 159 ms 17260 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 21096 KB Output is correct
2 Correct 230 ms 19188 KB Output is correct
3 Correct 158 ms 24300 KB Output is correct
4 Correct 220 ms 21100 KB Output is correct
5 Correct 236 ms 21372 KB Output is correct
6 Correct 192 ms 20972 KB Output is correct
7 Correct 230 ms 19052 KB Output is correct
8 Correct 179 ms 24432 KB Output is correct
9 Correct 117 ms 16624 KB Output is correct