oj.uz

답안 #876639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876639 2023-11-22T06:31:14 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
21.8254 / 100
 1000 ms 49868 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 = 400;

int mn[N], pr[N][20], pt[N], ind[N];
vector<int> edg[N];
vector<pii> vec[N];
vector<int> order;
bool mark[N];
set<pii> s;
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--){
		auto it = s.begin();
		int ind = it-> first;
		v = it-> second;
		mark[v] = 1;
		s.erase(it);
	}
	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--;

	//s.erase(s.find(make_pair(ind[x], x)));
	//cout<<"|n" << endl;
	pii p = find_pr(x);
	cout<< p.second <<"\n";
	x = p.first;
//	cout<< p.first <<"2\n";
	s.insert({ind[x], x});
	mark[x] = 0;
}

void read_query(){
	for(int i = 0; i < q; i++){
		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++){
		s.insert({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 add()':
ballmachine.cpp:62:7: warning: unused variable 'ind' [-Wunused-variable]
   62 |   int ind = it-> first;
      |       ^~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 18780 KB Time limit exceeded
2 Execution timed out 1085 ms 30924 KB Time limit exceeded
3 Incorrect 61 ms 31220 KB Output isn't correct
4 Execution timed out 1028 ms 18776 KB Time limit exceeded
5 Execution timed out 1055 ms 18780 KB Time limit exceeded
6 Incorrect 6 ms 19036 KB Output isn't correct
7 Execution timed out 1091 ms 19036 KB Time limit exceeded
8 Execution timed out 1065 ms 19036 KB Time limit exceeded
9 Incorrect 8 ms 19288 KB Output isn't correct
10 Incorrect 19 ms 20868 KB Output isn't correct
11 Incorrect 86 ms 31184 KB Output isn't correct
12 Incorrect 57 ms 31076 KB Output isn't correct
13 Incorrect 79 ms 31016 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24020 KB Output is correct
2 Incorrect 174 ms 43372 KB Output isn't correct
3 Incorrect 79 ms 36940 KB Output isn't correct
4 Execution timed out 1029 ms 26644 KB Time limit exceeded
5 Execution timed out 1060 ms 26196 KB Time limit exceeded
6 Incorrect 47 ms 26832 KB Output isn't correct
7 Incorrect 47 ms 25568 KB Output isn't correct
8 Correct 28 ms 23900 KB Output is correct
9 Incorrect 110 ms 43472 KB Output isn't correct
10 Incorrect 128 ms 43188 KB Output isn't correct
11 Incorrect 122 ms 43212 KB Output isn't correct
12 Execution timed out 1052 ms 39872 KB Time limit exceeded
13 Correct 87 ms 46800 KB Output is correct
14 Incorrect 79 ms 36940 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 30156 KB Output is correct
2 Incorrect 130 ms 40392 KB Output isn't correct
3 Correct 88 ms 44652 KB Output is correct
4 Incorrect 85 ms 39624 KB Output isn't correct
5 Incorrect 127 ms 39196 KB Output isn't correct
6 Incorrect 93 ms 39208 KB Output isn't correct
7 Incorrect 86 ms 36984 KB Output isn't correct
8 Correct 97 ms 44584 KB Output is correct
9 Incorrect 136 ms 43732 KB Output isn't correct
10 Incorrect 133 ms 43212 KB Output isn't correct
11 Incorrect 152 ms 43364 KB Output isn't correct
12 Incorrect 154 ms 40524 KB Output isn't correct
13 Correct 140 ms 49868 KB Output is correct
14 Correct 119 ms 37196 KB Output is correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 121 ms 43740 KB Output isn't correct
2 Incorrect 129 ms 40400 KB Output isn't correct
3 Correct 102 ms 49424 KB Output is correct
4 Incorrect 118 ms 43724 KB Output isn't correct
5 Incorrect 148 ms 43220 KB Output isn't correct
6 Incorrect 116 ms 43208 KB Output isn't correct
7 Incorrect 129 ms 40396 KB Output isn't correct
8 Correct 100 ms 49712 KB Output is correct
9 Incorrect 75 ms 37004 KB Output isn't correct