#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#include "lokahia.h"
int Q[205][205];
const int LIM = 400;
vector<int> ord;
int tq = 0;
int query(int i, int j){
if (i == j) return Q[i][i] = i;
else if (tq >= LIM) return -1;
else if (Q[i][j] == -2) {
tq++;
return Q[i][j] = Q[j][i] = CollectRelics(i,j);
}
else return Q[i][j];
}
int c[205];
int p[205];
int rk[205];
int sz[205];
void init(int n){
for (int i = 0; i < n; i++){
p[i] = i;
rk[i] = 0;
sz[i] = 1;
}
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
x = find(x) , y= find(y);
if (x == y) return;
if (rk[x] < rk[y]) swap(x,y);
p[y] = x;
sz[x] += sz[y];
if (rk[x] == rk[y]) rk[x]++;
}
vector<ii> v;
int FindBase(int N){
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) Q[i][j] = -2;
init(N);
ord.resize(N);
iota(ord.begin(), ord.end(), 0);
random_shuffle(ord.begin(),ord.end());
for (int i = 0; i < N/2; i++){
int Q = query(ord[2*i],ord[2*i+1]);
if (Q != -1){
c[Q]+=2;
un(Q, ord[2*i]);
un(Q, ord[2*i+1]);
}
else{
c[ord[2*i]]++;
c[ord[2*i+1]]++;
}
}
for (int i = 0; i < N; i++){
if (c[i]) v.push_back({c[i],i});
}
sort(v.begin(),v.end());
int st = v[0].second;
vector<int> good;
for (auto x : v){
if (find(x.second) != find(st)) good.push_back(x.second);
}
while (good.size() && tq <= LIM){
sort(good.begin(),good.end());
srand(time(NULL));
random_shuffle(good.begin(),good.end());
for (auto x : good){
if (st == x) continue;
int q = query(st,x);
if (q != -1){
if (q > st) st = q;
un(st,q);
}
else bad.push_back(x);
}
if (sz[find(st)] > N/2) return st;
vector<int> bad;
good.clear();
for (auto x : bad){
good.push_back(x);
}
bad.clear();
}
return -1;
}
Compilation message
lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:79:18: error: 'bad' was not declared in this scope
79 | else bad.push_back(x);
| ^~~
