제출 #876653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876653		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	21.83 / 100	434 ms	73956 KiB

ballmachine

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

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){
	for(auto p: vec[v]){
		int u = p.second;
		dfs_or(u);
	}
	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});
			flag = 1;
		}
		else{
			q2.push(tmp[i]);
		}
	}
	if(!flag)
		q2.push({ind[x], x});
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'void remove()':
ballmachine.cpp:99: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]
   99 |  for(int i = 0; i < tmp.size(); i++){
      |                 ~~^~~~~~~~~~~~
ballmachine.cpp: In function 'void reset()':
ballmachine.cpp:129: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]
  129 |  for(int i = 0; i < tmp.size(); i++)
      |                 ~~^~~~~~~~~~~~

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