oj.uz

Submission #876657

# Submission time Handle Problem Language Result Execution time Memory
876657 2023-11-22T07:29:00 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
21.8254 / 100
 525 ms 44316 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;
		}
		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;
}

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14684 KB Output isn't correct
2 Incorrect 302 ms 24236 KB Output isn't correct
3 Incorrect 243 ms 24516 KB Output isn't correct
4 Incorrect 2 ms 14680 KB Output isn't correct
5 Incorrect 3 ms 14680 KB Output isn't correct
6 Incorrect 4 ms 14684 KB Output isn't correct
7 Incorrect 3 ms 14684 KB Output isn't correct
8 Incorrect 4 ms 14684 KB Output isn't correct
9 Incorrect 16 ms 14940 KB Output isn't correct
10 Incorrect 42 ms 16088 KB Output isn't correct
11 Incorrect 316 ms 24268 KB Output isn't correct
12 Incorrect 242 ms 24688 KB Output isn't correct
13 Incorrect 356 ms 24356 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20936 KB Output is correct
2 Incorrect 401 ms 37392 KB Output isn't correct
3 Incorrect 409 ms 32188 KB Output isn't correct
4 Incorrect 167 ms 21532 KB Output isn't correct
5 Incorrect 177 ms 21580 KB Output isn't correct
6 Incorrect 193 ms 21176 KB Output isn't correct
7 Incorrect 190 ms 20140 KB Output isn't correct
8 Correct 72 ms 20952 KB Output is correct
9 Incorrect 437 ms 38356 KB Output isn't correct
10 Incorrect 399 ms 37424 KB Output isn't correct
11 Incorrect 476 ms 37404 KB Output isn't correct
12 Incorrect 435 ms 34456 KB Output isn't correct
13 Correct 347 ms 39820 KB Output is correct
14 Incorrect 399 ms 31888 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 26320 KB Output is correct
2 Incorrect 396 ms 34852 KB Output isn't correct
3 Correct 233 ms 38060 KB Output is correct
4 Incorrect 222 ms 33112 KB Output isn't correct
5 Incorrect 225 ms 32776 KB Output isn't correct
6 Incorrect 241 ms 32752 KB Output isn't correct
7 Incorrect 226 ms 30584 KB Output isn't correct
8 Correct 227 ms 38088 KB Output is correct
9 Incorrect 366 ms 38128 KB Output isn't correct
10 Incorrect 382 ms 37868 KB Output isn't correct
11 Incorrect 389 ms 37624 KB Output isn't correct
12 Incorrect 366 ms 35068 KB Output isn't correct
13 Correct 384 ms 44316 KB Output is correct
14 Correct 374 ms 32004 KB Output is correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 450 ms 37972 KB Output isn't correct
2 Incorrect 472 ms 34836 KB Output isn't correct
3 Correct 387 ms 44120 KB Output is correct
4 Incorrect 463 ms 37988 KB Output isn't correct
5 Incorrect 444 ms 37532 KB Output isn't correct
6 Incorrect 525 ms 37508 KB Output isn't correct
7 Incorrect 426 ms 34776 KB Output isn't correct
8 Correct 392 ms 44100 KB Output is correct
9 Incorrect 371 ms 31804 KB Output isn't correct