#include <bits/stdc++.h>
//#include "icc.h"
using namespace std;
const int maxn = 110;
int parent[maxn];
vector<int>comps[maxn];
/*bool query(int a, int b, int aa[], int bb[]) {
for(int i=0;i<a;i++) {
cout<<aa[i]<<" ";
} cout<<"\n";
for(int i=0;i<b;i++) {
cout<<bb[i]<<" ";
} cout<<"\n";
bool answ;
cin>>answ;
return answ;
}
void setRoad(int x, int y) {
cout<<"Road: "<<x<<" "<<y<<"\n";
}*/
int uroot(int x) {
while(x != parent[x]) x = parent[x];
return x;
}
void unite(int x, int y) {
x = uroot(x);
y = uroot(y);
if(x==y) return;
for(int i:comps[x]) {
comps[y].push_back(i);
}
parent[x] = y;
}
bool qq(set<int>a, set<int> b) {
int aa[a.size()], bb[b.size()];
int br = 0;
for(int i:a) aa[br++] = i;
br = 0;
for(int i:b) bb[br++] = i;
return query(a.size(), b.size(), aa, bb);
}
int bin(set<int>a, set<int>b) {
if(b.size() == 1) {
return (*(b.begin()));
}
set<int>x;
int br = 0;
int li = 0, ri = b.size() - 1;
vector<int>v;
for(int i:b) v.push_back(i);
while(li < ri) {
int mid = (li+ri)/2;
for(int i=li;i<=mid;i++) {
x.insert(v[i]);
}
if(qq(a, x)) ri = mid;
else li = mid + 1;
x.clear();
}
return v[li];
}
void run(int n) {
set<int>c;
for(int i=1;i<=n;i++) {
parent[i] = i;
comps[i].push_back(i);
}
for(int edges=1;edges<n;edges++) {
for(int i=1;i<=n;i++) {
c.insert(uroot(i));
}
for(int i=0;i<=7;i++) {
set<int>a, b;
for(int j:c) {
if(j&(1<<i)) for(int k:comps[j]) a.insert(k);
else for(int k:comps[j]) b.insert(k);
}
if(a.size() > 0 && b.size() > 0) {
if(qq(a, b)) {
int x = bin(a, b);
int y = bin(b, a);
setRoad(x, y);
unite(x, y);
break;
}
}
}
c.clear();
}
}
/*int main() {
run(4);
return 0;
}*/
Compilation message
icc.cpp: In function 'bool qq(std::set<int>, std::set<int>)':
icc.cpp:49:12: error: 'query' was not declared in this scope
return query(a.size(), b.size(), aa, bb);
^~~~~
icc.cpp: In function 'int bin(std::set<int>, std::set<int>)':
icc.cpp:57:9: warning: unused variable 'br' [-Wunused-variable]
int br = 0;
^~
icc.cpp: In function 'void run(int)':
icc.cpp:98:21: error: 'setRoad' was not declared in this scope
setRoad(x, y);
^~~~~~~
