oj.uz

Submission #306603

# Submission time Handle Problem Language Result Execution time Memory
306603 2020-09-26T00:48:22 Z Marlov Ball Machine (BOI13_ballmachine) C++14
16.2271 / 100
 103 ms 18808 KB 
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define maxN 100005

int N,Q;
int bl[maxN][16];
bool hasB[maxN];

//tree setup
vector<int> adj[maxN];
int stmin[maxN];
int ordering[maxN];

bool cmp(int a,int b){
	return stmin[a]<stmin[b];
}

void dfs1(int n,int p){
	if(adj[n].size()==0){
		stmin[n]=n;
		return;
	}
	for(int a:adj[n]) if(a!=p){
		dfs1(a,n);
	}
	sort(adj[n].begin(),adj[n].end(),cmp);
	stmin[n]=stmin[adj[n].front()];
}

int cno=0;
void dfs2(int n,int p){
	for(int a:adj[n]) if(n!=p){
		dfs2(a,n);
	}
	ordering[cno]=n;
	cno++;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>Q;
	int cnp;
	bl[N][0]=N;
	for(int i=0;i<N;i++){
		cin>>cnp;
		if(cnp==0){
			bl[i][0]=N;
		}else{
			cnp--;
		bl[i][0]=cnp;
		adj[cnp].push_back(i);
		}
		//adj[i].push_back(cnp);
	}
	
	for(int j=1;j<16;j++){
		for(int i=0;i<=N;i++){
			bl[i][j]=bl[bl[i][j-1]][j-1];
		}
	}
	//order-processing
	dfs1(0,-1);
	dfs2(0,-1);
	int t,v;
	for(int z=0;z<Q;z++){
		cin>>t>>v;
		if(t==1){
			for(int i=0;i<N;i++){
				if(hasB[ordering[i]]==false){
					hasB[ordering[i]]=true;
					v--;
				}
				if(v==0||i==N-1){
					cout<<ordering[i]+1<<'\n';
					break;
				}
			}
		}else if(t==2){
			int cn=v-1;
			int tl=0;
			for(int j=15;j>=0;j--){
				while(bl[cn][j]!=N&&hasB[bl[cn][j]]==true){
					cn=bl[cn][j];
					tl+=(1<<j);
				}
			}
				cout<<tl<<'\n';
				hasB[cn]=false; 
		}
	}
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2688 KB Output isn't correct
2 Incorrect 56 ms 8192 KB Output isn't correct
3 Correct 45 ms 8312 KB Output is correct
4 Incorrect 2 ms 2688 KB Output isn't correct
5 Incorrect 2 ms 2688 KB Output isn't correct
6 Incorrect 2 ms 2816 KB Output isn't correct
7 Incorrect 2 ms 2816 KB Output isn't correct
8 Incorrect 2 ms 2816 KB Output isn't correct
9 Incorrect 5 ms 3072 KB Output isn't correct
10 Incorrect 12 ms 4096 KB Output isn't correct
11 Incorrect 55 ms 8184 KB Output isn't correct
12 Correct 49 ms 8312 KB Output is correct
13 Incorrect 72 ms 8184 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6144 KB Output is correct
2 Incorrect 91 ms 13176 KB Output isn't correct
3 Correct 56 ms 10484 KB Output is correct
4 Incorrect 36 ms 5452 KB Output isn't correct
5 Incorrect 36 ms 5368 KB Output isn't correct
6 Incorrect 35 ms 5372 KB Output isn't correct
7 Incorrect 38 ms 5240 KB Output isn't correct
8 Correct 29 ms 6136 KB Output is correct
9 Incorrect 99 ms 16120 KB Output isn't correct
10 Incorrect 88 ms 13176 KB Output isn't correct
11 Incorrect 97 ms 11256 KB Output isn't correct
12 Incorrect 78 ms 11000 KB Output isn't correct
13 Correct 68 ms 13688 KB Output is correct
14 Correct 54 ms 10612 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 8952 KB Output isn't correct
2 Incorrect 95 ms 13048 KB Output isn't correct
3 Incorrect 64 ms 12536 KB Output isn't correct
4 Incorrect 49 ms 9848 KB Output isn't correct
5 Incorrect 51 ms 9464 KB Output isn't correct
6 Incorrect 50 ms 9464 KB Output isn't correct
7 Incorrect 62 ms 11128 KB Output isn't correct
8 Incorrect 60 ms 12536 KB Output isn't correct
9 Incorrect 74 ms 11640 KB Output isn't correct
10 Incorrect 75 ms 11256 KB Output isn't correct
11 Incorrect 87 ms 12280 KB Output isn't correct
12 Incorrect 93 ms 13176 KB Output isn't correct
13 Incorrect 90 ms 14200 KB Output isn't correct
14 Incorrect 68 ms 10612 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 11676 KB Output isn't correct
2 Incorrect 103 ms 13688 KB Output isn't correct
3 Correct 98 ms 18808 KB Output is correct
4 Incorrect 74 ms 11640 KB Output isn't correct
5 Incorrect 77 ms 11256 KB Output isn't correct
6 Incorrect 95 ms 14968 KB Output isn't correct
7 Incorrect 95 ms 13688 KB Output isn't correct
8 Correct 98 ms 18808 KB Output is correct
9 Correct 54 ms 10480 KB Output is correct