oj.uz

Submission #307300

# Submission time Handle Problem Language Result Execution time Memory
307300 2020-09-27T15:09:00 Z Marlov Ball Machine (BOI13_ballmachine) C++14
100 / 100
 161 ms 22392 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
#define INF 1000000000

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]=min(n,stmin[adj[n][0]]);
}

int cno=0;

void dfs2(int n){
	for(int i=0;i<adj[n].size();i++){
		dfs2(adj[n][i]);
	}
	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;
		}
		stmin[i]=INF;
		//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
*/

Compilation message

ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<adj[n].size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 71 ms 10564 KB Output is correct
3 Correct 56 ms 10492 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 6 ms 3200 KB Output is correct
10 Correct 14 ms 4608 KB Output is correct
11 Correct 67 ms 10488 KB Output is correct
12 Correct 57 ms 10488 KB Output is correct
13 Correct 66 ms 10492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6776 KB Output is correct
2 Correct 110 ms 17656 KB Output is correct
3 Correct 73 ms 13428 KB Output is correct
4 Correct 41 ms 7800 KB Output is correct
5 Correct 39 ms 7672 KB Output is correct
6 Correct 42 ms 7672 KB Output is correct
7 Correct 37 ms 6904 KB Output is correct
8 Correct 30 ms 6776 KB Output is correct
9 Correct 112 ms 18168 KB Output is correct
10 Correct 106 ms 17656 KB Output is correct
11 Correct 108 ms 17656 KB Output is correct
12 Correct 102 ms 15736 KB Output is correct
13 Correct 97 ms 19832 KB Output is correct
14 Correct 70 ms 13428 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 10488 KB Output is correct
2 Correct 119 ms 16192 KB Output is correct
3 Correct 100 ms 18168 KB Output is correct
4 Correct 81 ms 14972 KB Output is correct
5 Correct 77 ms 14584 KB Output is correct
6 Correct 83 ms 14584 KB Output is correct
7 Correct 83 ms 13304 KB Output is correct
8 Correct 101 ms 18168 KB Output is correct
9 Correct 134 ms 18296 KB Output is correct
10 Correct 129 ms 17784 KB Output is correct
11 Correct 131 ms 17916 KB Output is correct
12 Correct 120 ms 16252 KB Output is correct
13 Correct 161 ms 22392 KB Output is correct
14 Correct 88 ms 13936 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 18332 KB Output is correct
2 Correct 125 ms 16248 KB Output is correct
3 Correct 111 ms 21880 KB Output is correct
4 Correct 134 ms 18296 KB Output is correct
5 Correct 130 ms 17784 KB Output is correct
6 Correct 110 ms 17784 KB Output is correct
7 Correct 119 ms 16248 KB Output is correct
8 Correct 112 ms 21860 KB Output is correct
9 Correct 76 ms 13428 KB Output is correct