#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>fi, si;
int br = 0;
for(int i:b) {
if(br < (b.size()/2)) {
fi.insert(i); br++;
}
else si.insert(i);
}
if(qq(a, fi)) return bin(a, fi);
else return bin(a, si);
}
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(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:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(br < (b.size()/2)) {
~~~^~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:94:17: error: 'setRoad' was not declared in this scope
setRoad(x, y);
^~~~~~~
