oj.uz

Submission #145517

# Submission time Handle Problem Language Result Execution time Memory
145517 2019-08-20T10:27:51 Z miguel Ball Machine (BOI13_ballmachine) C++14
91.4286 / 100
 1000 ms 33164 KB 
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░*/
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
#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;
		}
	}
}

Compilation message

ballmachine.cpp:22:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 533 ms 19572 KB Output is correct
3 Correct 409 ms 19544 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 36 ms 3704 KB Output is correct
10 Correct 99 ms 7100 KB Output is correct
11 Correct 549 ms 19552 KB Output is correct
12 Correct 386 ms 19456 KB Output is correct
13 Correct 462 ms 19576 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 8732 KB Output is correct
2 Correct 907 ms 30032 KB Output is correct
3 Correct 416 ms 27416 KB Output is correct
4 Correct 421 ms 11484 KB Output is correct
5 Correct 501 ms 11412 KB Output is correct
6 Correct 482 ms 11396 KB Output is correct
7 Correct 456 ms 10660 KB Output is correct
8 Correct 286 ms 8796 KB Output is correct
9 Correct 705 ms 30328 KB Output is correct
10 Correct 880 ms 29944 KB Output is correct
11 Correct 760 ms 29924 KB Output is correct
12 Correct 778 ms 28568 KB Output is correct
13 Correct 489 ms 29344 KB Output is correct
14 Correct 412 ms 27380 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 16728 KB Output is correct
2 Correct 949 ms 29380 KB Output is correct
3 Correct 574 ms 26640 KB Output is correct
4 Correct 481 ms 24712 KB Output is correct
5 Correct 537 ms 24440 KB Output is correct
6 Correct 558 ms 24524 KB Output is correct
7 Correct 539 ms 23840 KB Output is correct
8 Correct 536 ms 26688 KB Output is correct
9 Correct 764 ms 30584 KB Output is correct
10 Execution timed out 1025 ms 30148 KB Time limit exceeded
11 Execution timed out 1061 ms 30204 KB Time limit exceeded
12 Correct 943 ms 29480 KB Output is correct
13 Execution timed out 1034 ms 33164 KB Time limit exceeded
14 Correct 539 ms 28012 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 30548 KB Output is correct
2 Correct 886 ms 29328 KB Output is correct
3 Correct 506 ms 32744 KB Output is correct
4 Correct 759 ms 30684 KB Output is correct
5 Correct 988 ms 30104 KB Output is correct
6 Correct 781 ms 30328 KB Output is correct
7 Correct 894 ms 29288 KB Output is correct
8 Correct 520 ms 32720 KB Output is correct
9 Correct 401 ms 27504 KB Output is correct