oj.uz

Submission #307054

# Submission time Handle Problem Language Result Execution time Memory
307054 2020-09-26T21:34:32 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][0]];
}

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 62 ms 9336 KB Output isn't correct
3 Execution timed out 1089 ms 9592 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 2 ms 2816 KB Output isn't correct
9 Incorrect 5 ms 3072 KB Output isn't correct
10 Incorrect 14 ms 4352 KB Output isn't correct
11 Incorrect 64 ms 9336 KB Output isn't correct
12 Execution timed out 1084 ms 9720 KB Time limit exceeded
13 Incorrect 62 ms 9336 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5992 KB Output is correct
2 Incorrect 102 ms 15480 KB Output isn't correct
3 Correct 71 ms 12436 KB Output is correct
4 Incorrect 41 ms 6776 KB Output isn't correct
5 Incorrect 38 ms 6656 KB Output isn't correct
6 Incorrect 37 ms 6648 KB Output isn't correct
7 Incorrect 38 ms 6008 KB Output isn't correct
8 Correct 30 ms 5880 KB Output is correct
9 Incorrect 103 ms 15992 KB Output isn't correct
10 Incorrect 111 ms 15608 KB Output isn't correct
11 Incorrect 103 ms 15480 KB Output isn't correct
12 Correct 97 ms 14072 KB Output is correct
13 Correct 94 ms 17272 KB Output is correct
14 Correct 69 ms 12408 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9336 KB Output is correct
2 Correct 117 ms 14476 KB Output is correct
3 Correct 96 ms 16024 KB Output is correct
4 Incorrect 74 ms 13432 KB Output isn't correct
5 Correct 78 ms 13048 KB Output is correct
6 Correct 81 ms 13048 KB Output is correct
7 Incorrect 78 ms 12024 KB Output isn't correct
8 Correct 96 ms 15992 KB Output is correct
9 Correct 125 ms 16120 KB Output is correct
10 Correct 123 ms 15736 KB Output is correct
11 Correct 125 ms 15736 KB Output is correct
12 Correct 116 ms 14456 KB Output is correct
13 Correct 160 ms 19448 KB Output is correct
14 Incorrect 89 ms 12608 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 16376 KB Output isn't correct
2 Incorrect 119 ms 14456 KB Output isn't correct
3 Correct 109 ms 19160 KB Output is correct
4 Incorrect 126 ms 16120 KB Output isn't correct
5 Incorrect 119 ms 15736 KB Output isn't correct
6 Incorrect 107 ms 15608 KB Output isn't correct
7 Incorrect 117 ms 14424 KB Output isn't correct
8 Correct 109 ms 19192 KB Output is correct
9 Correct 71 ms 12532 KB Output is correct