oj.uz

Submission #307049

# Submission time Handle Problem Language Result Execution time Memory
307049 2020-09-26T20:41:50 Z Marlov Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 19576 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];
int root;
//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){
	if(adj[n].size()==0){
		stmin[n]=n;
		return;
	}
	for(int a:adj[n]){
		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;
	N++;
	int cnp;
	bl[0][0]=0;
	for(int i=1;i<N;i++){
		cin>>cnp;
		if(cnp==0) root=i;
		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(root);
	dfs2(root);	
	int t,v;
	for(int z=0;z<Q;z++){
		cin>>t>>v;
		if(t==1){
			for(int i=1;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;
			int tl=0;
			for(int j=15;j>=0;j--){
				while(bl[cn][j]!=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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Incorrect 73 ms 9720 KB Output isn't correct
3 Execution timed out 1088 ms 9848 KB Time limit exceeded
4 Incorrect 2 ms 2688 KB Output isn't 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 5 ms 3200 KB Output isn't correct
10 Incorrect 13 ms 4352 KB Output isn't correct
11 Incorrect 62 ms 9720 KB Output isn't correct
12 Execution timed out 1089 ms 9760 KB Time limit exceeded
13 Incorrect 62 ms 9720 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 6272 KB Output isn't correct
2 Incorrect 95 ms 15736 KB Output isn't correct
3 Incorrect 70 ms 12664 KB Output isn't correct
4 Incorrect 41 ms 7160 KB Output isn't correct
5 Incorrect 40 ms 7036 KB Output isn't correct
6 Incorrect 36 ms 7040 KB Output isn't correct
7 Incorrect 37 ms 6400 KB Output isn't correct
8 Incorrect 28 ms 6264 KB Output isn't correct
9 Incorrect 91 ms 16124 KB Output isn't correct
10 Incorrect 95 ms 15608 KB Output isn't correct
11 Incorrect 97 ms 15608 KB Output isn't correct
12 Incorrect 94 ms 14200 KB Output isn't correct
13 Incorrect 97 ms 17284 KB Output isn't correct
14 Incorrect 69 ms 12536 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 9412 KB Output isn't correct
2 Incorrect 110 ms 14712 KB Output isn't correct
3 Incorrect 104 ms 15864 KB Output isn't correct
4 Incorrect 72 ms 13368 KB Output isn't correct
5 Incorrect 72 ms 13048 KB Output isn't correct
6 Incorrect 85 ms 13168 KB Output isn't correct
7 Incorrect 71 ms 11992 KB Output isn't correct
8 Incorrect 87 ms 15864 KB Output isn't correct
9 Incorrect 115 ms 16288 KB Output isn't correct
10 Incorrect 122 ms 15992 KB Output isn't correct
11 Incorrect 114 ms 15864 KB Output isn't correct
12 Incorrect 104 ms 14712 KB Output isn't correct
13 Incorrect 144 ms 19576 KB Output isn't correct
14 Incorrect 85 ms 12760 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 16376 KB Output isn't correct
2 Incorrect 107 ms 14712 KB Output isn't correct
3 Incorrect 102 ms 19192 KB Output isn't correct
4 Incorrect 121 ms 16416 KB Output isn't correct
5 Incorrect 113 ms 15864 KB Output isn't correct
6 Incorrect 95 ms 15864 KB Output isn't correct
7 Incorrect 103 ms 14584 KB Output isn't correct
8 Incorrect 100 ms 19192 KB Output isn't correct
9 Incorrect 66 ms 12532 KB Output isn't correct