nclude<bits/stdc++.h>
#include "icc.h"
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 1e5 + 7 , mod = 1e9 + 7 ;
const int inf = N ;
// How interesting!
int n ;
int fat[N] ;
vector<pair<int,int> > ed ;
int U , V ;
inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
void link(int u , int v){
u = find(u) ;
v = find(v) ;
if(u!=v)
fat[u] = v;
}
/*
bool ok(int u , int v){
if( u == U && v == V)
return 1 ;
if(u == V && v == U)
return 1;
return 0 ;
}
void setRoad(int u , int v){
if(ok(u , v))
link(u , v) ;
else{
cout<< u <<" "<< v <<">>" ;
cout<<"bad" ;
exit(0) ;
}
}
int query(int x , int y , vector<int> v1 , vector<int> v2){
set<int> st ;
for(auto u : v1)
st.insert(find(u)) ;
for(auto u : v2){
if(st.find(find(u)) != st.end())
return 1 ;
}
int m1 = 0 , m2 = 0 ;
for(auto u : v1)
if(u == U || u == V)
m1 = 1;
for(auto u : v2)
if(u == U || u == V)
m2 = 1 ;
if( m1 == 1 && m2 == 1 ){
return 1 ;
}
return 0 ;
}
*/
void divide(vector<vector<int> > &vec){
vector<vector<int> > ret ;
int sz = (int) vec.size() ;
for(int i = 0 ;i < sz ; ++ i){
int sz2 = (int) vec[i].size() ;
//if(sz2 < 2)continue ;
vector<int> lhs, rhs ;
for(int j = 0 ;j < sz2 ;++ j){
if(j < sz2 / 2 )
lhs.push_back(vec[i][j]) ;
else
rhs.push_back(vec[i][j]) ;
}
if(lhs.size())
ret.push_back(lhs) ;
if(rhs.size())
ret.push_back(rhs) ;
}
vec = ret ;
}
int conquer(vector<vector<int> > &vec, int lmt = 1000000){
int ret = 0 ;
vector<int> lhs, rhs ;
for(int i = 0 ; i < min(lmt , (int) vec.size() ) ; ++ i){
for(auto u : vec[i]){
if(i&1)rhs.push_back(u) ;
else lhs.push_back(u) ;
}
}
return query(lhs.size() , rhs.size() , lhs , rhs ) ;
}
void print(vector<vector<int> > &vec){
for(auto u : vec){
for(auto v : u )
cout<< v <<" " ;
cout<<"\n" ;
}
cout<<"----------\n" ;
}
void divide_or_conquer(vector<int> hs){
vector<vector<int> > dac { hs } ;
divide(dac) ;
int k = 0 ;
while(!conquer(dac)){
divide(dac) ;
break ;
}
int lo = 1, hi = (int) dac.size() ;
int lst = (int) dac.size() ;
while(lo<=hi){
int mid = (lo+hi) >> 1;
if(conquer(dac, mid)){
lst = mid ;
hi = mid - 1;
}else lo = mid + 1;
}
vector<int> qlhs = dac[lst-2] ,qrhs = dac[lst-1] ;
int llhs = 0 , rrhs = 0 ;
while(qlhs.size() && query(qlhs.size() , qrhs.size() , qlhs , qrhs )){
llhs = qlhs.back() ;
qlhs.pop_back() ;
}
if(llhs)qlhs.push_back(llhs) ;
while(qrhs.size() && query(qlhs.size() , qrhs.size() , qlhs , qrhs )){
rrhs = qrhs.back() ;
qrhs.pop_back() ;
}
if(rrhs)qrhs.push_back(rrhs) ;
int a = qlhs.back() , b = qrhs.back() ;
for(int i = 1;i <= n; ++ i){
for(int j = 1;j <= n ;++ j){
if(find(i) == a && find(j) == b && query(1 ,1 , {i} , {j})){
setRoad(i , j) ;
//cout<< i <<" " << j <<"()\n" ;
return ;
}
}
}
}
void run(int n){
for(int r = 0 ; r < n - 1; ++ r){
U = ed[r].first ;
V = ed[r].second ;
vector<int> v ;
for(int i = 1;i <= n; ++ i){
if(i == fat[i])
v.push_back(i) ;
}
divide_or_conquer(v) ;
}
}
Compilation message
icc.cpp:1:1: error: 'nclude' does not name a type
1 | nclude<bits/stdc++.h>
| ^~~~~~
icc.cpp:21:1: error: 'vector' does not name a type
21 | vector<pair<int,int> > ed ;
| ^~~~~~
icc.cpp:72:13: error: variable or field 'divide' declared void
72 | void divide(vector<vector<int> > &vec){
| ^~~~~~
icc.cpp:72:13: error: 'vector' was not declared in this scope
icc.cpp:3:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
2 | #include "icc.h"
+++ |+#include <vector>
3 |
icc.cpp:72:20: error: 'vector' was not declared in this scope
72 | void divide(vector<vector<int> > &vec){
| ^~~~~~
icc.cpp:72:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:72:27: error: expected primary-expression before 'int'
72 | void divide(vector<vector<int> > &vec){
| ^~~
icc.cpp:93:13: error: 'vector' was not declared in this scope
93 | int conquer(vector<vector<int> > &vec, int lmt = 1000000){
| ^~~~~~
icc.cpp:93:13: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:93:20: error: 'vector' was not declared in this scope
93 | int conquer(vector<vector<int> > &vec, int lmt = 1000000){
| ^~~~~~
icc.cpp:93:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:93:27: error: expected primary-expression before 'int'
93 | int conquer(vector<vector<int> > &vec, int lmt = 1000000){
| ^~~
icc.cpp:93:40: error: expected primary-expression before 'int'
93 | int conquer(vector<vector<int> > &vec, int lmt = 1000000){
| ^~~
icc.cpp:93:57: error: expression list treated as compound expression in initializer [-fpermissive]
93 | int conquer(vector<vector<int> > &vec, int lmt = 1000000){
| ^
icc.cpp:105:12: error: variable or field 'print' declared void
105 | void print(vector<vector<int> > &vec){
| ^~~~~~
icc.cpp:105:12: error: 'vector' was not declared in this scope
icc.cpp:105:12: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:105:19: error: 'vector' was not declared in this scope
105 | void print(vector<vector<int> > &vec){
| ^~~~~~
icc.cpp:105:19: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:105:26: error: expected primary-expression before 'int'
105 | void print(vector<vector<int> > &vec){
| ^~~
icc.cpp:114:24: error: variable or field 'divide_or_conquer' declared void
114 | void divide_or_conquer(vector<int> hs){
| ^~~~~~
icc.cpp:114:24: error: 'vector' was not declared in this scope
icc.cpp:114:24: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:114:31: error: expected primary-expression before 'int'
114 | void divide_or_conquer(vector<int> hs){
| ^~~
icc.cpp: In function 'void run(int)':
icc.cpp:163:21: error: 'ed' was not declared in this scope; did you mean 'ld'?
163 | U = ed[r].first ;
| ^~
| ld
icc.cpp:166:17: error: 'vector' was not declared in this scope
166 | vector<int> v ;
| ^~~~~~
icc.cpp:166:17: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
icc.cpp:166:24: error: expected primary-expression before 'int'
166 | vector<int> v ;
| ^~~
icc.cpp:169:33: error: 'v' was not declared in this scope
169 | v.push_back(i) ;
| ^
icc.cpp:171:35: error: 'v' was not declared in this scope
171 | divide_or_conquer(v) ;
| ^
icc.cpp:171:17: error: 'divide_or_conquer' was not declared in this scope
171 | divide_or_conquer(v) ;
| ^~~~~~~~~~~~~~~~~
