oj.uz

Submission #876651

# Submission time Handle Problem Language Result Execution time Memory
876651 2023-11-22T07:13:10 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
14.2857 / 100
 301 ms 73952 KB 
#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]);
		}
	}
	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

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: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.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 29532 KB Execution killed with signal 11
2 Runtime error 89 ms 46664 KB Execution killed with signal 11
3 Incorrect 149 ms 24236 KB Output isn't correct
4 Runtime error 13 ms 29748 KB Execution killed with signal 11
5 Runtime error 13 ms 29532 KB Execution killed with signal 11
6 Incorrect 3 ms 14684 KB Output isn't correct
7 Runtime error 16 ms 29668 KB Execution killed with signal 11
8 Runtime error 16 ms 29788 KB Execution killed with signal 11
9 Runtime error 17 ms 30276 KB Execution killed with signal 11
10 Runtime error 23 ms 31740 KB Execution killed with signal 11
11 Runtime error 71 ms 47072 KB Execution killed with signal 11
12 Incorrect 147 ms 24144 KB Output isn't correct
13 Runtime error 107 ms 47744 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 41452 KB Execution killed with signal 11
2 Runtime error 200 ms 71764 KB Execution killed with signal 11
3 Incorrect 272 ms 31508 KB Output isn't correct
4 Runtime error 40 ms 41560 KB Execution killed with signal 11
5 Runtime error 35 ms 41540 KB Execution killed with signal 11
6 Runtime error 47 ms 41624 KB Execution killed with signal 11
7 Runtime error 34 ms 39488 KB Execution killed with signal 11
8 Runtime error 38 ms 41448 KB Execution killed with signal 11
9 Runtime error 143 ms 73952 KB Execution killed with signal 11
10 Runtime error 191 ms 71636 KB Execution killed with signal 11
11 Runtime error 201 ms 73072 KB Execution killed with signal 11
12 Runtime error 171 ms 66640 KB Execution killed with signal 11
13 Incorrect 214 ms 39460 KB Output isn't correct
14 Incorrect 281 ms 31532 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25300 KB Output is correct
2 Incorrect 92 ms 32784 KB Output isn't correct
3 Correct 96 ms 36308 KB Output is correct
4 Incorrect 91 ms 31436 KB Output isn't correct
5 Incorrect 91 ms 31152 KB Output isn't correct
6 Incorrect 87 ms 31180 KB Output isn't correct
7 Incorrect 110 ms 28872 KB Output isn't correct
8 Correct 93 ms 36356 KB Output is correct
9 Incorrect 104 ms 36016 KB Output isn't correct
10 Incorrect 96 ms 35788 KB Output isn't correct
11 Incorrect 94 ms 35612 KB Output isn't correct
12 Incorrect 110 ms 32920 KB Output isn't correct
13 Correct 106 ms 42316 KB Output is correct
14 Correct 64 ms 29768 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 73584 KB Execution killed with signal 11
2 Runtime error 148 ms 66104 KB Execution killed with signal 11
3 Incorrect 295 ms 43788 KB Output isn't correct
4 Runtime error 180 ms 73788 KB Execution killed with signal 11
5 Runtime error 201 ms 72624 KB Execution killed with signal 11
6 Runtime error 238 ms 73192 KB Execution killed with signal 11
7 Runtime error 147 ms 66252 KB Execution killed with signal 11
8 Incorrect 301 ms 43796 KB Output isn't correct
9 Incorrect 273 ms 31528 KB Output isn't correct