#include<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;
}
int query1(int x , int y , vector<int> v1 , vector<int> v2){
int *v11;
int *v22 ;
v11 = new int[x] ;
v22 = new int [y] ;
for(int i = 0 ;i < x ; ++ i)
v11[i] = v1[i] ;
for(int i = 0 ;i < y ; ++ i)
v22[i] = v2[i] ;
return query(x , y , v11 , v22) ;
}
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 ;
}
vector<int> chd(int x){
vector<int> ret ;
for(int i = 1 ;i <= n; ++ i){
if(find(i) == x)
ret.push_back(i) ;
}
return 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)
for(auto v : chd(u))
rhs.push_back(v) ;
else for(auto v : chd(u))
lhs.push_back(v) ;
}
}
return query1(lhs.size() , rhs.size() , lhs , rhs ) ;
}
vector<int> qur(vector<int> ve){
vector<int> ret ;
for(auto u : ve)
for(auto v : chd(u))
ret.push_back(v) ;
return ret;
}
void getRoad(vector<int> v1, vector<int> v2){
vector<int> now = v1, oth = v2 ;
int lo = 1 , hi = v1.size() ;
int u = 0 , v = 0 ;
while(lo<=hi){
int mid = (lo+hi)>>1;
vector<int> nnow ;
for(int i = 0 ; i < mid ; ++ i)
nnow.push_back(now[i]) ;
if(query1(nnow.size() ,oth.size(),nnow,oth)){
hi = mid - 1;
u = nnow.back() ;
}else{
lo = mid + 1;
}
}
swap(now,oth) ;
swap(u , v) ;
lo = 1, hi = (int) now.size() ;
while(lo<=hi){
int mid = (lo+hi)>>1;
vector<int> nnow ;
for(int i = 0 ; i < mid ; ++ i)
nnow.push_back(now[i]) ;
if(query1(nnow.size() ,oth.size(),nnow,oth)){
hi = mid - 1;
u = nnow.back() ;
}else{
lo = mid + 1;
}
}
setRoad(u , v) ;
link(u , v) ;
}
void divide_or_conquer(vector<int> hs){
vector<vector<int> > dac { hs } ;
divide(dac) ;
while(!conquer(dac))divide(dac) ;
int lo = 1, hi = (int) dac.size();
int lst = (int) dac.size() ;
while(lo<=hi){
int mid = (lo+hi) >> 1;
if(conquer(dac, min((int)dac.size(),mid) )){
lst = mid ;
hi = mid - 1;
}else lo = mid + 1;
}
getRoad(qur(dac[lst-2]) , qur(dac[lst-1]) ) ;
}
void run(int x){
n = x;
for(int i = 1;i <= n; ++ i)
fat[i] = i ;
for(int r = 0 ; r < n - 1; ++ r){
vector<int> v ;
for(int i = 1;i <= n; ++ i){
if(i == fat[i])
v.push_back(i) ;
}
random_shuffle(v.begin() , v.end()) ;
divide_or_conquer(v) ;
}
}
Compilation message
icc.cpp: In function 'int conquer(std::vector<std::vector<int> >&, int)':
icc.cpp:76:13: warning: unused variable 'ret' [-Wunused-variable]
76 | int ret = 0 ;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
512 KB |
Ok! 136 queries used. |
| 2 |
Correct |
9 ms |
512 KB |
Ok! 130 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
632 KB |
Ok! 608 queries used. |
| 2 |
Correct |
54 ms |
632 KB |
Ok! 624 queries used. |
| 3 |
Correct |
55 ms |
632 KB |
Ok! 654 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
1016 KB |
Ok! 1506 queries used. |
| 2 |
Correct |
188 ms |
888 KB |
Ok! 1443 queries used. |
| 3 |
Correct |
200 ms |
1144 KB |
Ok! 1708 queries used. |
| 4 |
Correct |
191 ms |
1016 KB |
Ok! 1594 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
1016 KB |
Ok! 1673 queries used. |
| 2 |
Correct |
187 ms |
1020 KB |
Ok! 1534 queries used. |
| 3 |
Correct |
200 ms |
1016 KB |
Ok! 1617 queries used. |
| 4 |
Correct |
194 ms |
1016 KB |
Ok! 1610 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
1016 KB |
Ok! 1595 queries used. |
| 2 |
Correct |
206 ms |
1016 KB |
Ok! 1626 queries used. |
| 3 |
Correct |
206 ms |
1016 KB |
Ok! 1539 queries used. |
| 4 |
Correct |
196 ms |
1016 KB |
Ok! 1686 queries used. |
| 5 |
Correct |
196 ms |
1016 KB |
Ok! 1594 queries used. |
| 6 |
Correct |
191 ms |
1016 KB |
Ok! 1570 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
1016 KB |
Ok! 1615 queries used. |
| 2 |
Correct |
195 ms |
888 KB |
Ok! 1526 queries used. |
