oj.uz

Submission #111383

# Submission time Handle Problem Language Result Execution time Memory
111383 2019-05-15T05:03:06 Z rajarshi_basu Ball Machine (BOI13_ballmachine) C++14
16.7827 / 100
 677 ms 33916 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#include <fstream>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<ll,ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 

const ll INF = 4e18;
using namespace std;
const int MAXN = 100005;

vi g[MAXN];
int sparseTable[20][MAXN];
int DPmin[MAXN];
int dpt[MAXN];
int parent[MAXN];
set<ii> s;
int status[MAXN];

void dfs1(int node,int p){
	dpt[node] = ((p!=-1)?dpt[p]+1:0);
	parent[node] = p;
	vector<ii> all;
	DPmin[node] = node;
	for(auto e:g[node]){
		if(e==p)continue;
		dfs1(e,node);
		all.pb({DPmin[e],e});
		DPmin[node] = min(DPmin[node],DPmin[e]);
	}
	sort(all.begin(), all.end());
	g[node].clear();
	for(auto e:all)g[node].pb(e.ss);
	g[node].pb(p);
}
int T = 0;
int __tm__[MAXN];
void dfs2(int node,int p){
	for(auto e:g[node]){
		if(e!=p)dfs2(e,node);
	}
	__tm__[node] = T;
	s.insert({T++,node});
}
void buildSparseTable(int n){
	FOR(i,n)sparseTable[0][i] = parent[i];
	FORE(i,1,19){
		FOR(node,n){
			int p = sparseTable[i-1][node];
			if(p == -1){
				sparseTable[i][node] = -1;
			}else{
				sparseTable[i][node] = sparseTable[i-1][p];
			}
		}
		
	}
}
inline int findFirstAncestor(int n,int a){
	int k = 20;

	while(k--){
		int p = sparseTable[k][a];
		if(p == -1 or status[p] == 0){

		}else{
			a=p;
		}
	}
	return a;
}


int main(){
	int n,q;
	cin >> n >> q;
	FOR(i,n){
		int a;
		cin >> a;
		a--;
		if(a >= 0)g[a].pb(i);
	}
	dfs1(0,-1);
	dfs2(0,-1);
	buildSparseTable(n);
	while(q--){
		int t,a;
		cin >> t >> a;
		if(t == 1){
			int last = 0;
			FOR(i,a){
				ii to = *s.begin();
				s.erase(to);
				status[to.ss] = 1;
				last = to.ss+1;
			}
			cout << last << endl;
		}else{

			a--;
			int p = findFirstAncestor(n,a);
			s.insert({__tm__[p],p});
			status[p] = 0;
			
			cout << dpt[a]-dpt[p] << endl;
		}
	}
	return 0;
}

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2944 KB Output isn't correct
2 Incorrect 367 ms 12044 KB Output isn't correct
3 Correct 217 ms 10560 KB Output is correct
4 Incorrect 4 ms 2816 KB Output isn't correct
5 Incorrect 4 ms 2816 KB Output isn't correct
6 Incorrect 5 ms 2944 KB Output isn't correct
7 Incorrect 6 ms 2944 KB Output isn't correct
8 Incorrect 8 ms 2944 KB Output isn't correct
9 Incorrect 26 ms 3448 KB Output isn't correct
10 Incorrect 68 ms 5288 KB Output isn't correct
11 Incorrect 364 ms 12896 KB Output isn't correct
12 Correct 226 ms 10360 KB Output is correct
13 Incorrect 276 ms 10640 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 9720 KB Output is correct
2 Incorrect 609 ms 23288 KB Output isn't correct
3 Correct 256 ms 13144 KB Output is correct
4 Incorrect 247 ms 8676 KB Output isn't correct
5 Incorrect 266 ms 8588 KB Output isn't correct
6 Incorrect 206 ms 6976 KB Output isn't correct
7 Incorrect 230 ms 7800 KB Output isn't correct
8 Correct 170 ms 9720 KB Output is correct
9 Incorrect 630 ms 28620 KB Output isn't correct
10 Incorrect 604 ms 23164 KB Output isn't correct
11 Incorrect 341 ms 14628 KB Output isn't correct
12 Incorrect 420 ms 17272 KB Output isn't correct
13 Correct 285 ms 20472 KB Output is correct
14 Correct 296 ms 13160 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 15408 KB Output isn't correct
2 Incorrect 619 ms 24056 KB Output isn't correct
3 Incorrect 360 ms 19836 KB Output isn't correct
4 Incorrect 242 ms 14432 KB Output isn't correct
5 Incorrect 245 ms 14340 KB Output isn't correct
6 Incorrect 227 ms 14388 KB Output isn't correct
7 Incorrect 313 ms 19448 KB Output isn't correct
8 Incorrect 319 ms 19960 KB Output isn't correct
9 Incorrect 458 ms 18656 KB Output isn't correct
10 Incorrect 427 ms 18424 KB Output isn't correct
11 Incorrect 492 ms 21752 KB Output isn't correct
12 Incorrect 531 ms 24172 KB Output isn't correct
13 Incorrect 512 ms 23660 KB Output isn't correct
14 Incorrect 423 ms 18852 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 16740 KB Output isn't correct
2 Incorrect 677 ms 24596 KB Output isn't correct
3 Correct 481 ms 33916 KB Output is correct
4 Incorrect 418 ms 16836 KB Output isn't correct
5 Incorrect 379 ms 16248 KB Output isn't correct
6 Correct 521 ms 28436 KB Output is correct
7 Incorrect 609 ms 24584 KB Output isn't correct
8 Correct 345 ms 33788 KB Output is correct
9 Correct 241 ms 13044 KB Output is correct