oj.uz

Submission #307051

# Submission time Handle Problem Language Result Execution time Memory
307051 2020-09-26T21:00:37 Z Marlov Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 1000 ms 19448 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);
	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 64 ms 9464 KB Output isn't correct
3 Execution timed out 1094 ms 9464 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 2688 KB Output isn't correct
9 Incorrect 5 ms 3072 KB Output isn't correct
10 Incorrect 13 ms 4352 KB Output isn't correct
11 Incorrect 64 ms 9344 KB Output isn't correct
12 Execution timed out 1086 ms 9556 KB Time limit exceeded
13 Incorrect 65 ms 9336 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5880 KB Output is correct
2 Incorrect 106 ms 15480 KB Output isn't correct
3 Correct 71 ms 12404 KB Output is correct
4 Incorrect 40 ms 6784 KB Output isn't correct
5 Incorrect 39 ms 6776 KB Output isn't correct
6 Incorrect 38 ms 6648 KB Output isn't correct
7 Incorrect 38 ms 6016 KB Output isn't correct
8 Correct 30 ms 5888 KB Output is correct
9 Incorrect 103 ms 15876 KB Output isn't correct
10 Incorrect 110 ms 15480 KB Output isn't correct
11 Incorrect 102 ms 15608 KB Output isn't correct
12 Correct 96 ms 14072 KB Output is correct
13 Correct 91 ms 17272 KB Output is correct
14 Correct 71 ms 12572 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 113 ms 14456 KB Output is correct
3 Correct 95 ms 15992 KB Output is correct
4 Incorrect 76 ms 13304 KB Output isn't correct
5 Correct 84 ms 13048 KB Output is correct
6 Correct 76 ms 13048 KB Output is correct
7 Incorrect 73 ms 12024 KB Output isn't correct
8 Correct 97 ms 15992 KB Output is correct
9 Correct 126 ms 16248 KB Output is correct
10 Correct 114 ms 15684 KB Output is correct
11 Correct 112 ms 15736 KB Output is correct
12 Correct 117 ms 14456 KB Output is correct
13 Correct 168 ms 19448 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 122 ms 16120 KB Output isn't correct
2 Incorrect 120 ms 14556 KB Output isn't correct
3 Correct 107 ms 19192 KB Output is correct
4 Incorrect 121 ms 16208 KB Output isn't correct
5 Incorrect 120 ms 15704 KB Output isn't correct
6 Incorrect 109 ms 15608 KB Output isn't correct
7 Incorrect 111 ms 14456 KB Output isn't correct
8 Correct 106 ms 19192 KB Output is correct
9 Correct 69 ms 12408 KB Output is correct