oj.uz

답안 #876648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876648 2023-11-22T06:56:19 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 119 ms 131072 KB 
#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 = 330;

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());
		}
		tmp.push_back(q2.front());
	}
	
	while(q1.size())
		tmp.push_back(q1.front());
	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

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:123: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]
  123 |  for(int i = 0; i < tmp.size(); i++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 37904 KB Execution killed with signal 11
2 Runtime error 84 ms 131072 KB Execution killed with signal 9
3 Runtime error 68 ms 131072 KB Execution killed with signal 9
4 Runtime error 18 ms 37852 KB Execution killed with signal 11
5 Runtime error 19 ms 37980 KB Execution killed with signal 11
6 Runtime error 48 ms 131072 KB Execution killed with signal 9
7 Runtime error 19 ms 37980 KB Execution killed with signal 11
8 Runtime error 19 ms 38008 KB Execution killed with signal 11
9 Runtime error 48 ms 131072 KB Execution killed with signal 9
10 Runtime error 54 ms 131072 KB Execution killed with signal 9
11 Runtime error 69 ms 131072 KB Execution killed with signal 9
12 Runtime error 70 ms 131072 KB Execution killed with signal 9
13 Runtime error 77 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 55 ms 131072 KB Execution killed with signal 9
2 Runtime error 102 ms 131072 KB Execution killed with signal 9
3 Runtime error 81 ms 131072 KB Execution killed with signal 9
4 Runtime error 57 ms 131072 KB Execution killed with signal 9
5 Runtime error 57 ms 131072 KB Execution killed with signal 9
6 Runtime error 58 ms 131072 KB Execution killed with signal 9
7 Runtime error 61 ms 131072 KB Execution killed with signal 9
8 Runtime error 55 ms 131072 KB Execution killed with signal 9
9 Runtime error 99 ms 131072 KB Execution killed with signal 9
10 Runtime error 105 ms 131072 KB Execution killed with signal 9
11 Runtime error 108 ms 131072 KB Execution killed with signal 9
12 Runtime error 95 ms 131072 KB Execution killed with signal 9
13 Runtime error 92 ms 131072 KB Execution killed with signal 9
14 Runtime error 79 ms 131072 KB Execution killed with signal 9

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 67 ms 131072 KB Execution killed with signal 9
2 Runtime error 115 ms 131072 KB Execution killed with signal 9
3 Runtime error 85 ms 131072 KB Execution killed with signal 9
4 Runtime error 85 ms 131072 KB Execution killed with signal 9
5 Runtime error 87 ms 131072 KB Execution killed with signal 9
6 Runtime error 86 ms 131072 KB Execution killed with signal 9
7 Runtime error 83 ms 131072 KB Execution killed with signal 9
8 Runtime error 86 ms 131072 KB Execution killed with signal 9
9 Runtime error 94 ms 131072 KB Execution killed with signal 9
10 Runtime error 118 ms 131072 KB Execution killed with signal 9
11 Runtime error 101 ms 131072 KB Execution killed with signal 9
12 Runtime error 119 ms 131072 KB Execution killed with signal 9
13 Runtime error 106 ms 131072 KB Execution killed with signal 9
14 Runtime error 81 ms 131072 KB Execution killed with signal 9

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 101 ms 131072 KB Execution killed with signal 9
2 Runtime error 104 ms 131072 KB Execution killed with signal 9
3 Runtime error 98 ms 131072 KB Execution killed with signal 9
4 Runtime error 91 ms 131072 KB Execution killed with signal 9
5 Runtime error 108 ms 131072 KB Execution killed with signal 9
6 Runtime error 100 ms 131072 KB Execution killed with signal 9
7 Runtime error 103 ms 131072 KB Execution killed with signal 9
8 Runtime error 102 ms 131072 KB Execution killed with signal 9
9 Runtime error 82 ms 131072 KB Execution killed with signal 9