#include "icc.h"
#include <vector>
#include <cassert>
struct UnionFind{
std::vector<int> uf;
UnionFind(int N):uf(N){
for(int i=0;i<N;i++){
uf[i]=i;
}
}
int find(int a){
while(a!=uf[a]){
a=uf[a]=uf[uf[a]];
}
return a;
}
void merge(int a,int b){
uf[find(a)]=find(b);
}
int size(){
return uf.size();
}
bool isRoot(int a){
return a==uf[a];
}
}uf(0);
bool query1(std::vector<int> a,std::vector<int> b){
for(int& x:a) x++;
for(int& x:b) x++;
return query(a.size(),b.size(),a.data(),b.data());
}
template<class Iterator>
bool query1(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
return query1(std::vector<int>(b1,e1),std::vector<int>(b2,e2));
}
template<class Iterator>
std::pair<int,int> locate1(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
while(e1-b1>1){
Iterator m1=b1+(e1-b1)/2;
if(query1(b1,m1,b2,e2)){
e1=m1;
}else{
b1=m1;
}
}
while(e2-b2>1){
Iterator m2=b2+(e2-b2)/2;
if(query1(b1,e1,b2,m2)){
e2=m2;
}else{
b2=m2;
}
}
return std::pair<int,int>(*b1,*b2);
}
bool query2(std::vector<int> a,std::vector<int> b){
std::vector<int> c,d;
for(int i=0;i<uf.size();i++){
if(std::find(a.begin(),a.end(),uf.find(i))!=a.end()){
c.push_back(i+1);
}
if(std::find(b.begin(),b.end(),uf.find(i))!=b.end()){
d.push_back(i+1);
}
}
return query(c.size(),d.size(),c.data(),d.data());
}
template<class Iterator>
bool query2(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
return query2(std::vector<int>(b1,e1),std::vector<int>(b2,e2));
}
template<class Iterator>
std::pair<int,int> locate2(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
while(e1-b1>1){
Iterator m1=b1+(e1-b1)/2;
if(query2(b1,m1,b2,e2)){
e1=m1;
}else{
b1=m1;
}
}
while(e2-b2>1){
Iterator m2=b2+(e2-b2)/2;
if(query2(b1,e1,b2,m2)){
e2=m2;
}else{
b2=m2;
}
}
return std::pair<int,int>(*b1,*b2);
}
template<class Iterator>
std::pair<int,int> locate2(Iterator begin,Iterator end){
for(int k=0;(1<<k)<end-begin;k++){
std::vector<int> as,bs;
for(int i=0;i<end-begin;i++){
if(i&(1<<k)){
as.push_back(*(begin+i));
}else{
bs.push_back(*(begin+i));
}
}
if(query2(as,bs)){
return locate2(as.begin(),as.end(),bs.begin(),bs.end());
}
}
assert(0);
}
void solve(){
std::vector<int> reps;
for(int i=0;i<uf.size();i++){
if(uf.isRoot(i)){
reps.push_back(i);
}
}
std::pair<int,int> pair=locate2(reps.begin(),reps.end());
std::vector<int> as,bs;
for(int i=0;i<uf.size();i++){
if(uf.find(i)==uf.find(pair.first)){
as.push_back(i);
}
if(uf.find(i)==uf.find(pair.second)){
bs.push_back(i);
}
}
pair=locate1(as.begin(),as.end(),bs.begin(),bs.end());
setRoad(pair.first+1,pair.second+1);
uf.merge(pair.first,pair.second);
}
void run(int N){
uf=UnionFind(N);
for(int i=0;i<N-1;i++){
solve();
}
}
Compilation message
icc.cpp: In function 'bool query2(std::vector<int>, std::vector<int>)':
icc.cpp:65:13: error: 'find' is not a member of 'std'
if(std::find(a.begin(),a.end(),uf.find(i))!=a.end()){
^~~~
icc.cpp:65:13: note: suggested alternative: 'rend'
if(std::find(a.begin(),a.end(),uf.find(i))!=a.end()){
^~~~
rend
icc.cpp:68:13: error: 'find' is not a member of 'std'
if(std::find(b.begin(),b.end(),uf.find(i))!=b.end()){
^~~~
icc.cpp:68:13: note: suggested alternative: 'rend'
if(std::find(b.begin(),b.end(),uf.find(i))!=b.end()){
^~~~
rend
