oj.uz

Submission #145521

# Submission time Handle Problem Language Result Execution time Memory
145521 2019-08-20T10:32:53 Z miguel Ball Machine (BOI13_ballmachine) C++14
100 / 100
 654 ms 34408 KB 
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
const ll mod = 1000000007;
const ll nmax=100010;
#define int ll
int p[100010][18], n, q, root, subtree[100010], id[100010], cnt=1;
vi g[100010];
bool viz[100010];
set<pi> s;

int dfs(int nod){
	int mn=1e9;
	for(int i: g[nod]){
		mn=min(dfs(i), mn);
	}
	subtree[nod]=min(mn, nod);
	return subtree[nod];
}

void dfs_id(int nod){
	for(int i: g[nod]){
		dfs_id(i);
	}
	id[nod]=cnt;
	cnt++;
}

void dfs_p(int nod){
	for(int i=1; i<=17; i++) p[nod][i]=p[p[nod][i-1]][i-1];
	for(int i: g[nod]) dfs_p(i);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>q;
    for(int i=1; i<=n; i++){
		cin>>p[i][0];
		g[p[i][0]].pb(i);
		if(p[i][0]==0) root=i;
	}
	dfs(root);
	for(int i=1; i<=n; i++){
		if(g[i].size()) sort(g[i].begin(), g[i].end(), [](int a, int b){return (subtree[a]<subtree[b]);});
	}
	//id-s(order) and parents by lifting ye boi
	dfs_id(root);
	s.insert({(ll)1e9, 0LL});
	for(int i=1; i<=n; i++) s.insert({id[i], i});
	dfs_p(root);
	while(q--){
		int op, x;
		cin>>op>>x;
		if(op==1){
			for(int cnt=1; cnt<=x; cnt++){
				if(cnt==x) cout<<(*s.begin()).y<<"\n";
				viz[(*s.begin()).y]=1;
				s.erase(s.begin());
			}
		}
		else if(op==2){
			int cur=x, ans=0;
			for(int i=17; i>=0; i--){
				int nod=p[cur][i]; 
				if(nod!=0 && viz[nod]==1) cur=nod, ans+=(nod!=0)*(1<<i);
			}
			cout<<ans<<"\n";
			s.insert({id[cur], cur});
			viz[cur]=0;
			//for(pi i : s) cout<<i.y<<" "; cout<<endl;
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 523 ms 19604 KB Output is correct
3 Correct 384 ms 19456 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 9 ms 2936 KB Output is correct
9 Correct 34 ms 3832 KB Output is correct
10 Correct 92 ms 6884 KB Output is correct
11 Correct 488 ms 19548 KB Output is correct
12 Correct 387 ms 19584 KB Output is correct
13 Correct 430 ms 19560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 8996 KB Output is correct
2 Correct 561 ms 30704 KB Output is correct
3 Correct 398 ms 27524 KB Output is correct
4 Correct 327 ms 11640 KB Output is correct
5 Correct 335 ms 11748 KB Output is correct
6 Correct 326 ms 11512 KB Output is correct
7 Correct 322 ms 10660 KB Output is correct
8 Correct 260 ms 9056 KB Output is correct
9 Correct 569 ms 31120 KB Output is correct
10 Correct 556 ms 30680 KB Output is correct
11 Correct 520 ms 30712 KB Output is correct
12 Correct 531 ms 29020 KB Output is correct
13 Correct 470 ms 30604 KB Output is correct
14 Correct 401 ms 27364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 16940 KB Output is correct
2 Correct 617 ms 29720 KB Output is correct
3 Correct 388 ms 28024 KB Output is correct
4 Correct 370 ms 25336 KB Output is correct
5 Correct 376 ms 25080 KB Output is correct
6 Correct 381 ms 24960 KB Output is correct
7 Correct 373 ms 24048 KB Output is correct
8 Correct 393 ms 27996 KB Output is correct
9 Correct 619 ms 31424 KB Output is correct
10 Correct 650 ms 30940 KB Output is correct
11 Correct 654 ms 30924 KB Output is correct
12 Correct 612 ms 29788 KB Output is correct
13 Correct 631 ms 34408 KB Output is correct
14 Correct 523 ms 28192 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 31480 KB Output is correct
2 Correct 620 ms 29744 KB Output is correct
3 Correct 465 ms 34068 KB Output is correct
4 Correct 618 ms 31520 KB Output is correct
5 Correct 575 ms 30840 KB Output is correct
6 Correct 504 ms 30968 KB Output is correct
7 Correct 575 ms 29752 KB Output is correct
8 Correct 479 ms 33992 KB Output is correct
9 Correct 402 ms 27520 KB Output is correct