oj.uz

Submission #307057

# Submission time Handle Problem Language Result Execution time Memory
307057 2020-09-26T21:40:26 Z Marlov Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 1000 ms 19408 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(stmin[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
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Incorrect 60 ms 9336 KB Output isn't correct
3 Execution timed out 1086 ms 9592 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 3 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 6 ms 3200 KB Output isn't correct
10 Incorrect 16 ms 4480 KB Output isn't correct
11 Incorrect 64 ms 9336 KB Output isn't correct
12 Execution timed out 1084 ms 9720 KB Time limit exceeded
13 Incorrect 63 ms 9336 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5880 KB Output is correct
2 Incorrect 111 ms 15508 KB Output isn't correct
3 Correct 72 ms 12532 KB Output is correct
4 Incorrect 40 ms 6776 KB Output isn't correct
5 Incorrect 38 ms 6656 KB Output isn't correct
6 Incorrect 40 ms 6648 KB Output isn't correct
7 Incorrect 38 ms 6016 KB Output isn't correct
8 Correct 30 ms 5888 KB Output is correct
9 Incorrect 103 ms 15864 KB Output isn't correct
10 Incorrect 104 ms 15480 KB Output isn't correct
11 Incorrect 94 ms 15480 KB Output isn't correct
12 Correct 107 ms 14104 KB Output is correct
13 Correct 87 ms 17272 KB Output is correct
14 Correct 67 ms 12404 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9336 KB Output is correct
2 Correct 117 ms 14456 KB Output is correct
3 Correct 94 ms 15992 KB Output is correct
4 Incorrect 78 ms 13304 KB Output isn't correct
5 Correct 78 ms 13048 KB Output is correct
6 Correct 80 ms 13048 KB Output is correct
7 Incorrect 74 ms 12152 KB Output isn't correct
8 Correct 98 ms 15992 KB Output is correct
9 Correct 118 ms 16120 KB Output is correct
10 Correct 118 ms 15652 KB Output is correct
11 Correct 121 ms 15864 KB Output is correct
12 Correct 117 ms 14460 KB Output is correct
13 Correct 153 ms 19408 KB Output is correct
14 Incorrect 90 ms 12660 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 16120 KB Output isn't correct
2 Incorrect 112 ms 14584 KB Output isn't correct
3 Correct 110 ms 19288 KB Output is correct
4 Incorrect 132 ms 16124 KB Output isn't correct
5 Incorrect 123 ms 15736 KB Output isn't correct
6 Incorrect 106 ms 15608 KB Output isn't correct
7 Incorrect 110 ms 14456 KB Output isn't correct
8 Correct 109 ms 19192 KB Output is correct
9 Correct 70 ms 12416 KB Output is correct