oj.uz

Submission #306587

# Submission time Handle Problem Language Result Execution time Memory
306587 2020-09-25T23:12:24 Z Marlov Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 1000 ms 21496 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]=stmin[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 62 ms 8568 KB Output isn't correct
3 Execution timed out 1087 ms 9068 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 3104 KB Output isn't correct
10 Incorrect 13 ms 4224 KB Output isn't correct
11 Incorrect 64 ms 8696 KB Output isn't correct
12 Execution timed out 1083 ms 9268 KB Time limit exceeded
13 Incorrect 61 ms 8568 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6264 KB Output is correct
2 Incorrect 112 ms 15864 KB Output isn't correct
3 Correct 67 ms 11380 KB Output is correct
4 Incorrect 40 ms 6912 KB Output isn't correct
5 Incorrect 40 ms 6776 KB Output isn't correct
6 Incorrect 37 ms 6776 KB Output isn't correct
7 Incorrect 39 ms 6008 KB Output isn't correct
8 Correct 30 ms 6264 KB Output is correct
9 Incorrect 99 ms 16248 KB Output isn't correct
10 Incorrect 98 ms 15864 KB Output isn't correct
11 Incorrect 95 ms 15864 KB Output isn't correct
12 Correct 102 ms 13688 KB Output is correct
13 Correct 95 ms 19064 KB Output is correct
14 Correct 63 ms 11252 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9592 KB Output is correct
2 Correct 105 ms 14072 KB Output is correct
3 Correct 88 ms 17528 KB Output is correct
4 Incorrect 68 ms 13692 KB Output isn't correct
5 Correct 74 ms 13292 KB Output is correct
6 Correct 72 ms 13308 KB Output is correct
7 Incorrect 75 ms 11768 KB Output isn't correct
8 Correct 95 ms 17472 KB Output is correct
9 Correct 110 ms 16632 KB Output is correct
10 Correct 111 ms 16120 KB Output is correct
11 Correct 109 ms 16120 KB Output is correct
12 Correct 105 ms 14072 KB Output is correct
13 Correct 141 ms 21496 KB Output is correct
14 Incorrect 83 ms 11508 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 16504 KB Output isn't correct
2 Incorrect 103 ms 14072 KB Output isn't correct
3 Correct 106 ms 21112 KB Output is correct
4 Incorrect 121 ms 16504 KB Output isn't correct
5 Incorrect 122 ms 16120 KB Output isn't correct
6 Incorrect 102 ms 15992 KB Output isn't correct
7 Incorrect 106 ms 14104 KB Output isn't correct
8 Correct 102 ms 21112 KB Output is correct
9 Correct 64 ms 11252 KB Output is correct