oj.uz

Submission #145514

# Submission time Handle Problem Language Result Execution time Memory
145514 2019-08-20T10:23:53 Z miguel Ball Machine (BOI13_ballmachine) C++14
93.7302 / 100
 1000 ms 34668 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];
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";
				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 && (s.size()==0 || s.find(make_pair(id[nod], nod))==s.end())) cur=nod, ans+=(nod!=0)*(1<<i);
			}
			cout<<ans<<"\n";
			s.insert({id[cur], cur});
			//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 2936 KB Output is correct
2 Correct 540 ms 19428 KB Output is correct
3 Correct 397 ms 19496 KB Output is correct
4 Correct 5 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 38 ms 3796 KB Output is correct
10 Correct 103 ms 6904 KB Output is correct
11 Correct 556 ms 19588 KB Output is correct
12 Correct 392 ms 19476 KB Output is correct
13 Correct 470 ms 19448 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 8888 KB Output is correct
2 Correct 925 ms 30704 KB Output is correct
3 Correct 463 ms 27328 KB Output is correct
4 Correct 453 ms 11688 KB Output is correct
5 Correct 514 ms 11660 KB Output is correct
6 Correct 479 ms 11500 KB Output is correct
7 Correct 460 ms 10548 KB Output is correct
8 Correct 290 ms 9024 KB Output is correct
9 Correct 722 ms 31044 KB Output is correct
10 Correct 942 ms 30480 KB Output is correct
11 Correct 840 ms 30712 KB Output is correct
12 Correct 884 ms 28936 KB Output is correct
13 Correct 521 ms 30444 KB Output is correct
14 Correct 421 ms 27324 KB Output is correct

Subtask #3
34.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 16888 KB Output is correct
2 Correct 918 ms 29716 KB Output is correct
3 Correct 561 ms 27824 KB Output is correct
4 Correct 488 ms 25336 KB Output is correct
5 Correct 585 ms 24980 KB Output is correct
6 Correct 594 ms 24972 KB Output is correct
7 Correct 561 ms 24124 KB Output is correct
8 Correct 560 ms 27768 KB Output is correct
9 Correct 761 ms 31236 KB Output is correct
10 Correct 988 ms 30888 KB Output is correct
11 Correct 999 ms 30932 KB Output is correct
12 Execution timed out 1076 ms 29708 KB Time limit exceeded
13 Execution timed out 1002 ms 34668 KB Time limit exceeded
14 Correct 563 ms 27860 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 31496 KB Output is correct
2 Correct 950 ms 29764 KB Output is correct
3 Correct 571 ms 34224 KB Output is correct
4 Correct 763 ms 31352 KB Output is correct
5 Execution timed out 1074 ms 30840 KB Time limit exceeded
6 Correct 824 ms 31012 KB Output is correct
7 Correct 971 ms 29728 KB Output is correct
8 Correct 624 ms 34040 KB Output is correct
9 Correct 446 ms 27504 KB Output is correct