Submission #876639

#	Time	Username	Problem	Language	Result	Execution time	Memory
876639		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	21.83 / 100	1091 ms	49868 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
const int maxn = 1e6;
const ll mod = 998244353;
const int sq = 400;

int mn[N], pr[N][20], pt[N], ind[N];
vector<int> edg[N];
vector<pii> vec[N];
vector<int> order;
bool mark[N];
set<pii> s;
int n, q, rot;

void input(){
	cin>> n>> q;
	for(int i = 0; i < n; i++){
		int p;	cin>> p;
		if(p == 0)
			rot = i;
		else{
			p--;
			edg[p].push_back(i);
			edg[i].push_back(p);
		}
	}
}


void dfs(int v, int p){
	mn[v] = v;
	for(int u: edg[v]){
		if(u != p){	
			pr[u][0] = v;
			for(int i = 1; i < 20; i++)
				pr[u][i] = pr[pr[u][i - 1]][i - 1];
			dfs(u, v);
			vec[v].push_back({mn[u], u});
			mn[v] = min(mn[v], u);
		}
	}
}

void dfs_or(int v){
	while(pt[v] < (v == rot? edg[v].size(): edg[v].size() - 1)){
		int u = vec[v][pt[v]].second;
		dfs_or(u);
		pt[v]++;
	}
	order.push_back(v);
	ind[v] = order.size() - 1;
}

void add(){
	int k;	cin>> k;
	int v = 0;//	cin>> v;
	while(k--){
		auto it = s.begin();
		int ind = it-> first;
		v = it-> second;
		mark[v] = 1;
		s.erase(it);
	}
	cout<< v + 1 <<"\n";
}

pii find_pr(int v){
	int cnt = 0;
	for(int i = 19; i >= 0; i--){
		if(mark[pr[v][i]]){
			//cout<< i <<" " << pr[v][i] <<"\n";
			v = pr[v][i];
			cnt += (1 << i);
		}
	}
	return make_pair(v, cnt);
}
void remove(){
	int x;	cin>> x;
	x--;

	//s.erase(s.find(make_pair(ind[x], x)));
	//cout<<"|n" << endl;
	pii p = find_pr(x);
	cout<< p.second <<"\n";
	x = p.first;
//	cout<< p.first <<"2\n";
	s.insert({ind[x], x});
	mark[x] = 0;
}

void read_query(){
	for(int i = 0; i < q; i++){
		int t;	cin>> t;
		if(t == 1){
			add();
		}
		else{
			remove();
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	input();
	for(int i = 0; i <= n; i++){
		for(int j = 0; j < 20; j++)
			pr[i][j] = n;
	}
	
	dfs(rot, -1);
	for(int i = 0; i < n; i++)
		sort(vec[i].begin(), vec[i].end());
	dfs_or(rot);
	for(int i = 0; i < n; i++){
		s.insert({i, order[i]});
	}
	
	read_query();
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs_or(int)':
ballmachine.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  while(pt[v] < (v == rot? edg[v].size(): edg[v].size() - 1)){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void add()':
ballmachine.cpp:62:7: warning: unused variable 'ind' [-Wunused-variable]
   62 |   int ind = it-> first;
      |       ^~~

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 14.285714285714286 / 40
• Subtask 4: 1.1111111111111112 / 5