oj.uz

답안 #111386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111386 2019-05-15T05:11:43 Z rajarshi_basu Ball Machine (BOI13_ballmachine) C++14
100 / 100
 886 ms 39860 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;
	int root = 0;
	FOR(i,n){
		int a;
		cin >> a;
		a--;
		if(a >= 0)g[a].pb(i);
		else root = i;
	}

	dfs1(root,-1);
	dfs2(root,-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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 504 ms 15524 KB Output is correct
3 Correct 331 ms 15608 KB Output is correct
4 Correct 4 ms 2716 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 6 ms 2944 KB Output is correct
7 Correct 9 ms 2944 KB Output is correct
8 Correct 9 ms 2944 KB Output is correct
9 Correct 28 ms 3584 KB Output is correct
10 Correct 95 ms 5880 KB Output is correct
11 Correct 551 ms 15472 KB Output is correct
12 Correct 353 ms 15452 KB Output is correct
13 Correct 357 ms 15480 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 9744 KB Output is correct
2 Correct 812 ms 30840 KB Output is correct
3 Correct 378 ms 21924 KB Output is correct
4 Correct 386 ms 11384 KB Output is correct
5 Correct 460 ms 11256 KB Output is correct
6 Correct 410 ms 11372 KB Output is correct
7 Correct 405 ms 9464 KB Output is correct
8 Correct 204 ms 9592 KB Output is correct
9 Correct 755 ms 30812 KB Output is correct
10 Correct 806 ms 30968 KB Output is correct
11 Correct 702 ms 30812 KB Output is correct
12 Correct 792 ms 25884 KB Output is correct
13 Correct 431 ms 34908 KB Output is correct
14 Correct 351 ms 21980 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 16856 KB Output is correct
2 Correct 724 ms 26568 KB Output is correct
3 Correct 391 ms 32120 KB Output is correct
4 Correct 391 ms 25476 KB Output is correct
5 Correct 427 ms 25208 KB Output is correct
6 Correct 491 ms 25348 KB Output is correct
7 Correct 460 ms 22008 KB Output is correct
8 Correct 407 ms 32368 KB Output is correct
9 Correct 698 ms 31060 KB Output is correct
10 Correct 760 ms 31020 KB Output is correct
11 Correct 791 ms 30920 KB Output is correct
12 Correct 756 ms 26756 KB Output is correct
13 Correct 693 ms 39860 KB Output is correct
14 Correct 515 ms 22540 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 718 ms 31040 KB Output is correct
2 Correct 886 ms 26748 KB Output is correct
3 Correct 442 ms 39212 KB Output is correct
4 Correct 715 ms 31080 KB Output is correct
5 Correct 742 ms 30924 KB Output is correct
6 Correct 615 ms 30840 KB Output is correct
7 Correct 685 ms 26692 KB Output is correct
8 Correct 374 ms 39160 KB Output is correct
9 Correct 367 ms 22068 KB Output is correct