oj.uz

Submission #307053

# Submission time Handle Problem Language Result Execution time Memory
307053 2020-09-26T21:29:29 Z Marlov Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 1000 ms 19328 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][18];
bool hasB[maxN];
int root;
//tree setup
vector<int> adj[maxN];
int stmin[maxN];
int ordering[maxN];
int layer[maxN];

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

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

int cno=0;

void dfs2(int n){
	for(int a:adj[n]){
		dfs2(a);
	}
	ordering[cno]=n;
	cno++;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//ifstream cin("check.in");
	//ofstream cout("check.out");
	cin>>N>>Q;
	int cnp;
	for(int i=0;i<N;i++){
		cin>>cnp;
		cnp--;
		if(cnp==-1){
			root=i;
			bl[i][0]=i;
		}else{
			adj[cnp].push_back(i);
			bl[i][0]=cnp;
		}
		//adj[i].push_back(cnp);
	}
	for(int j=1;j<18;j++){
		for(int i=0;i<N;i++){
			bl[i][j]=bl[bl[i][j-1]][j-1];
		}
	}
	//order-processing
	layer[root]=0;
	dfs1(root);
	dfs2(root);	
	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=17;j>=0;j--){
				if(hasB[bl[cn][j]]==true){
					//cout<<"HERE: "<<layer[bl[cn][j]]<<" and "<<layer[cn]<<'\n';
					tl+=layer[cn]-layer[bl[cn][j]];
					cn=bl[cn][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
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Incorrect 63 ms 9336 KB Output isn't correct
3 Execution timed out 1095 ms 9516 KB Time limit exceeded
4 Correct 2 ms 2688 KB Output is correct
5 Incorrect 2 ms 2688 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 6 ms 3200 KB Output isn't correct
10 Incorrect 14 ms 4352 KB Output isn't correct
11 Incorrect 62 ms 9464 KB Output isn't correct
12 Execution timed out 1092 ms 9668 KB Time limit exceeded
13 Incorrect 100 ms 9464 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5888 KB Output is correct
2 Incorrect 105 ms 15480 KB Output isn't correct
3 Correct 70 ms 12404 KB Output is correct
4 Incorrect 42 ms 6904 KB Output isn't correct
5 Incorrect 38 ms 6648 KB Output isn't correct
6 Incorrect 38 ms 6656 KB Output isn't correct
7 Incorrect 39 ms 6016 KB Output isn't correct
8 Correct 30 ms 5880 KB Output is correct
9 Incorrect 108 ms 15864 KB Output isn't correct
10 Incorrect 101 ms 15480 KB Output isn't correct
11 Incorrect 99 ms 15480 KB Output isn't correct
12 Correct 99 ms 14072 KB Output is correct
13 Correct 90 ms 17228 KB Output is correct
14 Correct 72 ms 12404 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9336 KB Output is correct
2 Correct 117 ms 14428 KB Output is correct
3 Correct 88 ms 15992 KB Output is correct
4 Incorrect 76 ms 13304 KB Output isn't correct
5 Correct 75 ms 13176 KB Output is correct
6 Correct 73 ms 13048 KB Output is correct
7 Incorrect 70 ms 12024 KB Output isn't correct
8 Correct 90 ms 15992 KB Output is correct
9 Correct 121 ms 16120 KB Output is correct
10 Correct 129 ms 15736 KB Output is correct
11 Correct 121 ms 15736 KB Output is correct
12 Correct 123 ms 14456 KB Output is correct
13 Correct 154 ms 19328 KB Output is correct
14 Incorrect 83 ms 12532 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 16252 KB Output isn't correct
2 Incorrect 109 ms 14456 KB Output isn't correct
3 Correct 102 ms 19192 KB Output is correct
4 Incorrect 118 ms 16120 KB Output isn't correct
5 Incorrect 116 ms 15736 KB Output isn't correct
6 Incorrect 101 ms 15608 KB Output isn't correct
7 Incorrect 109 ms 14456 KB Output isn't correct
8 Correct 103 ms 19192 KB Output is correct
9 Correct 71 ms 12532 KB Output is correct