oj.uz

Submission #876649

# Submission time Handle Problem Language Result Execution time Memory
876649 2023-11-22T06:59:00 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
14.2857 / 100
 305 ms 78776 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 = 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

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

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 37976 KB Execution killed with signal 11
2 Runtime error 104 ms 55356 KB Execution killed with signal 11
3 Incorrect 150 ms 28456 KB Output isn't correct
4 Runtime error 18 ms 37980 KB Execution killed with signal 11
5 Runtime error 20 ms 37876 KB Execution killed with signal 11
6 Incorrect 4 ms 18776 KB Output isn't correct
7 Runtime error 18 ms 38180 KB Execution killed with signal 11
8 Runtime error 18 ms 38316 KB Execution killed with signal 11
9 Runtime error 22 ms 38492 KB Execution killed with signal 11
10 Runtime error 28 ms 40176 KB Execution killed with signal 11
11 Runtime error 76 ms 55768 KB Execution killed with signal 11
12 Incorrect 153 ms 28468 KB Output isn't correct
13 Runtime error 104 ms 56360 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 45684 KB Execution killed with signal 11
2 Runtime error 201 ms 76488 KB Execution killed with signal 11
3 Incorrect 281 ms 33876 KB Output isn't correct
4 Runtime error 41 ms 49944 KB Execution killed with signal 11
5 Runtime error 38 ms 49984 KB Execution killed with signal 11
6 Runtime error 51 ms 50092 KB Execution killed with signal 11
7 Runtime error 42 ms 47928 KB Execution killed with signal 11
8 Runtime error 42 ms 45544 KB Execution killed with signal 11
9 Runtime error 164 ms 78776 KB Execution killed with signal 11
10 Runtime error 220 ms 76540 KB Execution killed with signal 11
11 Runtime error 212 ms 78144 KB Execution killed with signal 11
12 Runtime error 178 ms 71452 KB Execution killed with signal 11
13 Incorrect 230 ms 43812 KB Output isn't correct
14 Incorrect 277 ms 33888 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27596 KB Output is correct
2 Incorrect 104 ms 35564 KB Output isn't correct
3 Correct 96 ms 40712 KB Output is correct
4 Incorrect 88 ms 35992 KB Output isn't correct
5 Incorrect 118 ms 35564 KB Output isn't correct
6 Incorrect 116 ms 35476 KB Output isn't correct
7 Incorrect 88 ms 33240 KB Output isn't correct
8 Correct 97 ms 40552 KB Output is correct
9 Incorrect 92 ms 38660 KB Output isn't correct
10 Incorrect 103 ms 38092 KB Output isn't correct
11 Incorrect 111 ms 38104 KB Output isn't correct
12 Incorrect 107 ms 35284 KB Output isn't correct
13 Correct 106 ms 44656 KB Output is correct
14 Correct 68 ms 32072 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 78576 KB Execution killed with signal 11
2 Runtime error 146 ms 70772 KB Execution killed with signal 11
3 Incorrect 305 ms 46208 KB Output isn't correct
4 Runtime error 180 ms 78320 KB Execution killed with signal 11
5 Runtime error 216 ms 77340 KB Execution killed with signal 11
6 Runtime error 244 ms 77896 KB Execution killed with signal 11
7 Runtime error 148 ms 70856 KB Execution killed with signal 11
8 Incorrect 300 ms 46160 KB Output isn't correct
9 Incorrect 285 ms 33872 KB Output isn't correct