oj.uz

Submission #306585

# Submission time Handle Problem Language Result Execution time Memory
306585 2020-09-25T22:58:42 Z Marlov Ball Machine (BOI13_ballmachine) C++14
18.0342 / 100
 1000 ms 22648 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]=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;
	N++;
	bl[0][0]=0;
	int cnp;
	for(int i=1;i<N;i++){
		cin>>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 i=0;i<Q;i++){
		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]<<'\n';
					break;
				}
			}
		}else if(t==2){
			int cn=v;
			int tl=0;
			for(int j=15;j>=0;j--){
				while(cn!=0&&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
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Incorrect 60 ms 9720 KB Output isn't correct
3 Execution timed out 1045 ms 9720 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 2944 KB Output isn't correct
8 Incorrect 2 ms 2816 KB Output isn't correct
9 Incorrect 6 ms 3200 KB Output isn't correct
10 Incorrect 13 ms 4352 KB Output isn't correct
11 Incorrect 64 ms 9720 KB Output isn't correct
12 Execution timed out 1089 ms 9756 KB Time limit exceeded
13 Incorrect 74 ms 9720 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6784 KB Output is correct
2 Incorrect 110 ms 17400 KB Output isn't correct
3 Execution timed out 1073 ms 12504 KB Time limit exceeded
4 Incorrect 41 ms 7672 KB Output isn't correct
5 Incorrect 42 ms 7552 KB Output isn't correct
6 Incorrect 41 ms 7672 KB Output isn't correct
7 Incorrect 37 ms 6648 KB Output isn't correct
8 Correct 30 ms 6776 KB Output is correct
9 Incorrect 98 ms 17656 KB Output isn't correct
10 Incorrect 108 ms 17336 KB Output isn't correct
11 Incorrect 111 ms 17400 KB Output isn't correct
12 Incorrect 97 ms 15096 KB Output isn't correct
13 Correct 90 ms 20088 KB Output is correct
14 Execution timed out 1098 ms 12404 KB Time limit exceeded

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 10232 KB Output isn't correct
2 Incorrect 111 ms 15480 KB Output isn't correct
3 Correct 97 ms 18552 KB Output is correct
4 Incorrect 78 ms 14584 KB Output isn't correct
5 Incorrect 74 ms 14200 KB Output isn't correct
6 Incorrect 75 ms 14200 KB Output isn't correct
7 Incorrect 76 ms 12792 KB Output isn't correct
8 Correct 91 ms 18456 KB Output is correct
9 Incorrect 114 ms 17784 KB Output isn't correct
10 Incorrect 121 ms 17376 KB Output isn't correct
11 Incorrect 116 ms 17308 KB Output isn't correct
12 Incorrect 118 ms 15608 KB Output isn't correct
13 Correct 145 ms 22648 KB Output is correct
14 Incorrect 86 ms 13044 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17784 KB Output isn't correct
2 Incorrect 108 ms 15480 KB Output isn't correct
3 Correct 104 ms 22264 KB Output is correct
4 Incorrect 111 ms 17784 KB Output isn't correct
5 Incorrect 111 ms 17400 KB Output isn't correct
6 Incorrect 111 ms 17400 KB Output isn't correct
7 Incorrect 108 ms 15480 KB Output isn't correct
8 Correct 104 ms 22392 KB Output is correct
9 Execution timed out 1091 ms 12468 KB Time limit exceeded