oj.uz

Submission #41057

# Submission time Handle Problem Language Result Execution time Memory
41057 2018-02-12T07:59:52 Z Kerim Ball Machine (BOI13_ballmachine) C++14
100 / 100
 363 ms 69640 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>adj[MAXN];
int dp[MAXN],id[MAXN],cnt,P[MAXN][18],vis[MAXN],n;
set<PII>s;
bool cmp(int x,int y){
	return (dp[x]<dp[y]);
}
void pre(int nd){
	dp[nd]=nd;
	if(adj[nd].size()==0)
		return;
	tr(it,adj[nd])
		pre(*it),umin(dp[nd],dp[*it]);
	sort(all(adj[nd]),cmp);		
}
vector<int>v;
void dfs(int nd){
	tr(it,adj[nd])	
		P[*it][0]=nd,dfs(*it);
	id[nd]=++cnt;
}
void build(){
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			if(~P[i][j-1])
				P[i][j]=P[P[i][j-1]][j-1];
}
int main(){
	memset(P,-1,sizeof P);
    //~ freopen("file.in", "r", stdin);
    int q,root;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
		int p;
		scanf("%d",&p);
		if(!p)
			root=i;
		else
			adj[p].pb(i);
	}
	pre(root);dfs(root);
	build();
	for(int i=1;i<=n;i++)
		s.insert(mp(id[i],i));
	while(q--){
		int t,k,ans=0;
		scanf("%d%d",&t,&k);
		if(t==1){
			__typeof((s).begin())it=s.begin();
			while(k--){
				vis[it->ss]=1;
				ans=it->ss;
				s.erase(it++);
			}
		}
		else{
			for(int j=17;j>=0;j--)
				if(~P[k][j] and vis[P[k][j]])
					k=P[k][j],ans+=(1<<j);	
			vis[k]=0;
			s.insert(mp(id[k],k));	
		}	
		printf("%d\n",ans);		
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:50: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:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
                 ^
ballmachine.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t,&k);
                      ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 167 ms 16032 KB Output is correct
3 Correct 108 ms 16948 KB Output is correct
4 Correct 8 ms 16948 KB Output is correct
5 Correct 9 ms 16948 KB Output is correct
6 Correct 9 ms 16948 KB Output is correct
7 Correct 9 ms 16948 KB Output is correct
8 Correct 9 ms 16948 KB Output is correct
9 Correct 17 ms 16948 KB Output is correct
10 Correct 36 ms 16948 KB Output is correct
11 Correct 172 ms 18928 KB Output is correct
12 Correct 108 ms 19672 KB Output is correct
13 Correct 138 ms 20772 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 20772 KB Output is correct
2 Correct 219 ms 28000 KB Output is correct
3 Correct 126 ms 28000 KB Output is correct
4 Correct 89 ms 28000 KB Output is correct
5 Correct 92 ms 28000 KB Output is correct
6 Correct 85 ms 28000 KB Output is correct
7 Correct 87 ms 28000 KB Output is correct
8 Correct 53 ms 28000 KB Output is correct
9 Correct 201 ms 34372 KB Output is correct
10 Correct 204 ms 35196 KB Output is correct
11 Correct 175 ms 36536 KB Output is correct
12 Correct 229 ms 36624 KB Output is correct
13 Correct 147 ms 40940 KB Output is correct
14 Correct 126 ms 40940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 40940 KB Output is correct
2 Correct 247 ms 41192 KB Output is correct
3 Correct 167 ms 44084 KB Output is correct
4 Correct 164 ms 44084 KB Output is correct
5 Correct 162 ms 44084 KB Output is correct
6 Correct 162 ms 44084 KB Output is correct
7 Correct 164 ms 44084 KB Output is correct
8 Correct 175 ms 48472 KB Output is correct
9 Correct 264 ms 49516 KB Output is correct
10 Correct 334 ms 50496 KB Output is correct
11 Correct 265 ms 51872 KB Output is correct
12 Correct 319 ms 52024 KB Output is correct
13 Correct 271 ms 58176 KB Output is correct
14 Correct 239 ms 58176 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 58176 KB Output is correct
2 Correct 258 ms 58176 KB Output is correct
3 Correct 205 ms 62992 KB Output is correct
4 Correct 363 ms 62992 KB Output is correct
5 Correct 288 ms 62992 KB Output is correct
6 Correct 266 ms 63996 KB Output is correct
7 Correct 307 ms 64160 KB Output is correct
8 Correct 202 ms 69640 KB Output is correct
9 Correct 140 ms 69640 KB Output is correct