Submission #876649

#	Time	Username	Problem	Language	Result	Execution time	Memory
876649		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	14.29 / 100	305 ms	78776 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 = 335;

int mn[N], pr[N][20], pt[N], ind[N];
vector<int> edg[N];
vector<pii> vec[N];
vector<int> order;
bool mark[N];
queue<pii> q1, q2;
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--){
		int f1 = (q1.size()? q1.front().first: 1e5 + 10);
		int f2 = (q2.size()? q2.front().first: 1e5 + 10);
		if(f1 < f2){
			v = q1.front().second;
			mark[v] = 1;
			q1.pop();
		}
		else{
			v = q2.front().second;
			mark[v] = 1;
			q2.pop();
		}
	}
	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--;
	pii p = find_pr(x);
	cout<< p.second <<"\n";
	x = p.first;
	vector<pii> tmp;
	while(q2.size()){
		tmp.push_back(q2.front());
		q2.pop();
	}
	bool flag = 0;
	for(int i = 0; i < tmp.size(); i++){
		if(!flag && tmp[i].first > ind[x]){
			q2.push({ind[x], x});
		}
		else{
			q2.push(tmp[i]);
		}
	}
	mark[x] = 0;
}

void reset(){
	vector<pii> tmp;
	while(q2.size()){
		pii p = q2.front();
		while(q1.size() && q1.front().first < p.first){
			tmp.push_back(q1.front());
			q1.pop();
		}
		tmp.push_back(q2.front());
		q2.pop();
	}
	
	while(q1.size()){
		tmp.push_back(q1.front());
		q1.pop();
	}
	for(int i = 0; i < tmp.size(); i++)
		q1.push(tmp[i]);
}

void read_query(){
	for(int i = 0; i < q; i++){
		if(i && i % sq == 0)
			reset();
		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++){
		q1.push({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 remove()':
ballmachine.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < tmp.size(); i++){
      |                 ~~^~~~~~~~~~~~
ballmachine.cpp: In function 'void reset()':
ballmachine.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i = 0; i < tmp.size(); i++)
      |                 ~~^~~~~~~~~~~~

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