oj.uz

Submission #306588

# Submission time Handle Problem Language Result Execution time Memory
306588 2020-09-25T23:18:27 Z Marlov Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 1000 ms 21484 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 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]<<'\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 63 ms 8668 KB Output isn't correct
3 Execution timed out 1086 ms 8740 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 13 ms 4224 KB Output isn't correct
11 Incorrect 62 ms 8568 KB Output isn't correct
12 Execution timed out 1041 ms 8824 KB Time limit exceeded
13 Incorrect 60 ms 8568 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6264 KB Output is correct
2 Incorrect 99 ms 15864 KB Output isn't correct
3 Correct 66 ms 11248 KB Output is correct
4 Incorrect 44 ms 6948 KB Output isn't correct
5 Incorrect 40 ms 6904 KB Output isn't correct
6 Incorrect 37 ms 6776 KB Output isn't correct
7 Incorrect 40 ms 6008 KB Output isn't correct
8 Correct 30 ms 6272 KB Output is correct
9 Incorrect 108 ms 16248 KB Output isn't correct
10 Incorrect 107 ms 15864 KB Output isn't correct
11 Incorrect 95 ms 15864 KB Output isn't correct
12 Correct 96 ms 13688 KB Output is correct
13 Correct 92 ms 19064 KB Output is correct
14 Correct 65 ms 11252 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9592 KB Output is correct
2 Correct 111 ms 14108 KB Output is correct
3 Correct 92 ms 17528 KB Output is correct
4 Incorrect 70 ms 13688 KB Output isn't correct
5 Correct 74 ms 13308 KB Output is correct
6 Correct 80 ms 13304 KB Output is correct
7 Incorrect 73 ms 11768 KB Output isn't correct
8 Correct 90 ms 17528 KB Output is correct
9 Correct 122 ms 16504 KB Output is correct
10 Correct 120 ms 16120 KB Output is correct
11 Correct 116 ms 16120 KB Output is correct
12 Correct 120 ms 14072 KB Output is correct
13 Correct 159 ms 21484 KB Output is correct
14 Incorrect 83 ms 11380 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 16504 KB Output isn't correct
2 Incorrect 105 ms 14072 KB Output isn't correct
3 Correct 107 ms 21240 KB Output is correct
4 Incorrect 112 ms 16504 KB Output isn't correct
5 Incorrect 113 ms 16064 KB Output isn't correct
6 Incorrect 101 ms 15992 KB Output isn't correct
7 Incorrect 108 ms 14072 KB Output isn't correct
8 Correct 109 ms 21112 KB Output is correct
9 Correct 65 ms 11248 KB Output is correct