oj.uz

Submission #67978

# Submission time Handle Problem Language Result Execution time Memory
67978 2018-08-15T16:24:12 Z thebes Ball Machine (BOI13_ballmachine) C++14
16.7827 / 100
 206 ms 69244 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN=1e5+5,LG=19;
int sp[MN][LG], N, Q, i, j, x, y, mn[MN], p[MN], nxt, fl[MN];
priority_queue<tuple<int,int>> q;
vector<int> adj[MN];
int dfs(int n){
	mn[n] = n;
	for(auto v : adj[n])
		mn[n] = min(mn[n], dfs(v));
	return mn[n];
}
void ord(int n){
	sort(adj[n].begin(),adj[n].end(),[](int i,int j){return mn[i]<mn[j];});
	for(auto v : adj[n]) ord(v);
	p[n] = nxt--; q.push({p[n],n});
}
int main(){
	for(scanf("%d%d",&N,&Q),i=1;i<=N;i++){
		scanf("%d",&x); sp[i][0]=x;
		adj[x].push_back(i);
	}
	dfs(1), ord(1);
	for(j=1;j<LG;j++){
		for(i=1;i<=N;i++)
			sp[i][j]=sp[sp[i][j-1]][j-1];
	}
	for(;Q;Q--){
		scanf("%d%d",&x,&y);
		if(x == 1){
			int ans = 0;
			while(q.size()&&y){
				fl[get<1>(q.top())]=1;
				ans=get<1>(q.top()); q.pop(); y--;
			}
			printf("%d\n",ans);
		}
		else{
			int ans = 0;
			for(i=LG-1;i>=0;i--)
				if(fl[sp[y][i]]) ans+=1<<i, y=sp[y][i];
			printf("%d\n",ans);
			fl[y] = 0; q.push({p[y],y});
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d%d",&N,&Q),i=1;i<=N;i++){
      ~~~~~~~~~~~~~~~~~~~^~~~
ballmachine.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x); sp[i][0]=x;
   ~~~~~^~~~~~~~~
ballmachine.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Incorrect 99 ms 10608 KB Output isn't correct
3 Correct 67 ms 11316 KB Output is correct
4 Incorrect 4 ms 11316 KB Output isn't correct
5 Incorrect 4 ms 11316 KB Output isn't correct
6 Incorrect 6 ms 11316 KB Output isn't correct
7 Incorrect 5 ms 11316 KB Output isn't correct
8 Incorrect 5 ms 11316 KB Output isn't correct
9 Incorrect 14 ms 11316 KB Output isn't correct
10 Incorrect 26 ms 11316 KB Output isn't correct
11 Incorrect 92 ms 13592 KB Output isn't correct
12 Correct 70 ms 13968 KB Output is correct
13 Incorrect 86 ms 15184 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15184 KB Output is correct
2 Incorrect 187 ms 23912 KB Output isn't correct
3 Correct 81 ms 23912 KB Output is correct
4 Incorrect 76 ms 23912 KB Output isn't correct
5 Incorrect 87 ms 23912 KB Output isn't correct
6 Incorrect 80 ms 23912 KB Output isn't correct
7 Incorrect 76 ms 23912 KB Output isn't correct
8 Correct 54 ms 23912 KB Output is correct
9 Incorrect 177 ms 33812 KB Output isn't correct
10 Incorrect 177 ms 33812 KB Output isn't correct
11 Incorrect 114 ms 33812 KB Output isn't correct
12 Incorrect 129 ms 33812 KB Output isn't correct
13 Correct 98 ms 34784 KB Output is correct
14 Correct 83 ms 34784 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 34784 KB Output isn't correct
2 Incorrect 167 ms 38312 KB Output isn't correct
3 Incorrect 116 ms 38312 KB Output isn't correct
4 Incorrect 84 ms 38312 KB Output isn't correct
5 Incorrect 89 ms 38312 KB Output isn't correct
6 Incorrect 76 ms 38312 KB Output isn't correct
7 Incorrect 122 ms 40312 KB Output isn't correct
8 Incorrect 95 ms 42600 KB Output isn't correct
9 Incorrect 151 ms 43004 KB Output isn't correct
10 Incorrect 136 ms 43900 KB Output isn't correct
11 Incorrect 157 ms 47032 KB Output isn't correct
12 Incorrect 170 ms 49264 KB Output isn't correct
13 Incorrect 159 ms 51888 KB Output isn't correct
14 Incorrect 130 ms 51888 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 51888 KB Output isn't correct
2 Incorrect 186 ms 55384 KB Output isn't correct
3 Correct 141 ms 62528 KB Output is correct
4 Incorrect 133 ms 62528 KB Output isn't correct
5 Incorrect 157 ms 62528 KB Output isn't correct
6 Correct 196 ms 62528 KB Output is correct
7 Incorrect 161 ms 62528 KB Output isn't correct
8 Correct 206 ms 69244 KB Output is correct
9 Correct 86 ms 69244 KB Output is correct