oj.uz

Submission #30530

# Submission time Handle Problem Language Result Execution time Memory
30530 2017-07-24T12:36:33 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 289 ms 22100 KB 
//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int> adj[maxn], post; 
int prior[maxn], dep[maxn], par[maxn][18];
bool has[maxn]; 
int MinDfs(int u) {
	prior[u] = u; 
	for(int v : adj[u]) {
		dep[v] = dep[u] + 1;
		prior[u] = min(prior[u], MinDfs(v)); 
	}
	sort(adj[u].begin(), adj[u].end(), [](int &a, int &b) { return prior[a] < prior[b]; } ); 
	return prior[u];
} 
void postDfs(int u) { 
	for(int i = 1; i <= 17; i++) 
		if(par[u][i-1]) 
			par[u][i] = par[par[u][i-1]][i-1]; 

	if(!adj[u].size()) { post.push_back(u); return; }
	for(int v : adj[u]) postDfs(v); 
	post.push_back(u);
}

struct node{
	int u, prior; 
	bool operator < (const node &p) const {
		return prior > p.prior; 
	}
};

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, q, root; 
	scanf("%d %d", &n, &q); 
	for(int i = 1; i <= n; i++) {
		int p; scanf("%d", &p); 
		if(p == 0) root = i;
		adj[p].push_back(i);  
		par[i][0] = p;
	} 
	MinDfs(root); 
	postDfs(root); 
	priority_queue<node> Q; 
	for(int i = 0; i < n; i++) {
		Q.push({post[i], i});
		prior[post[i]] = i;
		has[post[i]] = 0;
	}
	while(q--) {
		int c, x; 
		scanf("%d %d", &c, &x); 
		if(c == 1) {
			node u; 
			while(x--) {
				u = Q.top();
				has[u.u] = 1;
				Q.pop();  
			} printf("%d\n", u.u);
		} else {
			int y = x; 
			for(int i = 17; i >= 0; i--) if(par[y][i]) {
				if(has[par[y][i]]) y = par[y][i];
			}
			has[y] = 0;
			printf("%d\n",dep[x] - dep[y]);
			Q.push({y, prior[y]}); 
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q); 
                        ^
ballmachine.cpp:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p); 
                         ^
ballmachine.cpp:57:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &c, &x); 
                         ^
ballmachine.cpp:48:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  postDfs(root); 
               ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12276 KB Output is correct
2 Correct 149 ms 14412 KB Output is correct
3 Correct 69 ms 14412 KB Output is correct
4 Correct 0 ms 12276 KB Output is correct
5 Correct 0 ms 12276 KB Output is correct
6 Correct 3 ms 12276 KB Output is correct
7 Correct 0 ms 12276 KB Output is correct
8 Correct 3 ms 12276 KB Output is correct
9 Correct 9 ms 12408 KB Output is correct
10 Correct 29 ms 12804 KB Output is correct
11 Correct 136 ms 14412 KB Output is correct
12 Correct 96 ms 14412 KB Output is correct
13 Correct 126 ms 14412 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14180 KB Output is correct
2 Correct 276 ms 18584 KB Output is correct
3 Correct 123 ms 15840 KB Output is correct
4 Correct 103 ms 14164 KB Output is correct
5 Correct 96 ms 14040 KB Output is correct
6 Correct 99 ms 14040 KB Output is correct
7 Correct 106 ms 13616 KB Output is correct
8 Correct 36 ms 14176 KB Output is correct
9 Correct 279 ms 19000 KB Output is correct
10 Correct 243 ms 18580 KB Output is correct
11 Correct 196 ms 18580 KB Output is correct
12 Correct 229 ms 17340 KB Output is correct
13 Correct 136 ms 21184 KB Output is correct
14 Correct 106 ms 15840 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 15620 KB Output is correct
2 Correct 279 ms 17416 KB Output is correct
3 Correct 186 ms 20536 KB Output is correct
4 Correct 219 ms 18060 KB Output is correct
5 Correct 159 ms 17732 KB Output is correct
6 Correct 196 ms 17732 KB Output is correct
7 Correct 173 ms 16792 KB Output is correct
8 Correct 99 ms 20532 KB Output is correct
9 Correct 179 ms 19000 KB Output is correct
10 Correct 279 ms 18588 KB Output is correct
11 Correct 279 ms 18592 KB Output is correct
12 Correct 263 ms 17408 KB Output is correct
13 Correct 289 ms 22100 KB Output is correct
14 Correct 143 ms 15844 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 18996 KB Output is correct
2 Correct 243 ms 17408 KB Output is correct
3 Correct 189 ms 22096 KB Output is correct
4 Correct 226 ms 18996 KB Output is correct
5 Correct 239 ms 18588 KB Output is correct
6 Correct 206 ms 18588 KB Output is correct
7 Correct 289 ms 17416 KB Output is correct
8 Correct 216 ms 22100 KB Output is correct
9 Correct 99 ms 15844 KB Output is correct