oj.uz

Submission #306602

# Submission time Handle Problem Language Result Execution time Memory
306602 2020-09-26T00:45:42 Z Marlov Ball Machine (BOI13_ballmachine) C++14
16.2271 / 100
 104 ms 18936 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){
			v--;
			int cn=v;
			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 2 ms 2688 KB Output isn't correct
2 Incorrect 53 ms 8144 KB Output isn't correct
3 Correct 47 ms 8312 KB Output is correct
4 Incorrect 2 ms 2688 KB Output isn't correct
5 Incorrect 2 ms 2816 KB Output isn't correct
6 Incorrect 2 ms 2816 KB Output isn't correct
7 Incorrect 3 ms 2816 KB Output isn't correct
8 Incorrect 3 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 53 ms 8184 KB Output isn't correct
12 Correct 47 ms 8312 KB Output is correct
13 Incorrect 69 ms 8056 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6136 KB Output is correct
2 Incorrect 89 ms 13156 KB Output isn't correct
3 Correct 54 ms 10484 KB Output is correct
4 Incorrect 35 ms 5504 KB Output isn't correct
5 Incorrect 35 ms 5368 KB Output isn't correct
6 Incorrect 36 ms 5368 KB Output isn't correct
7 Incorrect 36 ms 5120 KB Output isn't correct
8 Correct 29 ms 6136 KB Output is correct
9 Incorrect 96 ms 16120 KB Output isn't correct
10 Incorrect 89 ms 13180 KB Output isn't correct
11 Incorrect 92 ms 11248 KB Output isn't correct
12 Incorrect 79 ms 11000 KB Output isn't correct
13 Correct 68 ms 13560 KB Output is correct
14 Correct 56 ms 10484 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 8960 KB Output isn't correct
2 Incorrect 92 ms 13152 KB Output isn't correct
3 Incorrect 71 ms 12536 KB Output isn't correct
4 Incorrect 47 ms 9816 KB Output isn't correct
5 Incorrect 51 ms 9464 KB Output isn't correct
6 Incorrect 52 ms 9472 KB Output isn't correct
7 Incorrect 61 ms 11128 KB Output isn't correct
8 Incorrect 63 ms 12536 KB Output isn't correct
9 Incorrect 81 ms 11640 KB Output isn't correct
10 Incorrect 80 ms 11256 KB Output isn't correct
11 Incorrect 87 ms 12280 KB Output isn't correct
12 Incorrect 95 ms 13048 KB Output isn't correct
13 Incorrect 93 ms 14200 KB Output isn't correct
14 Incorrect 69 ms 10764 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11640 KB Output isn't correct
2 Incorrect 104 ms 13688 KB Output isn't correct
3 Correct 98 ms 18808 KB Output is correct
4 Incorrect 80 ms 11608 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 101 ms 13688 KB Output isn't correct
8 Correct 100 ms 18936 KB Output is correct
9 Correct 54 ms 10484 KB Output is correct