# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1271837 | ZeroCool | ICC (CEOI16_icc) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include “icc.h”
using namespace std;;
#define ll long long
#define ar array
#define ld double
#define int long long
#define all(v) v.begin(), v.end()
// #pragma GCC optimize("O3,Ofast,unroll-loops ")
const int N = 3010;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;
int MOD = 1e9 + 7;
const ld EPS = 1e-12;
template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};
struct DSU{
vector<int> p;
DSU(int n){
p.resize(n);
iota(all(p), 0);
}
int fnd(int x){
if(p[x] == x)return x;
return p[x] = fnd(p[x]);
}
bool upd(int a,int b){
a = fnd(a);
b = fnd(b);
if(a == b)return 0;
p[a] = b;
return 1;
}
};
void run(int n){
DSU dsu(n);
for(int it = 0;it < n - 1;it++){
map<int, vector<int> > mp;
for(int i = 0;i < n;i++)mp[dsu.fnd(i)].push_back(i);
vector<vector<int> > C;
for(auto [a, b]: mp)C.push_back(b);
for(int j = 1;j < C.size();j *= 2){
vector<int> v[2];
for(int i = 0;i < C.size();i++){
for(auto u: C[i]){
if(j & i)v[1].push_back(u);
else v[0].push_back(u);
}
}
if(ask(v[0], v[1])){
int lo = -1, hi = v[0].size();
while(hi - lo > 1){
int mid = (lo + hi) / 2;
vector<int> q;
for(int i = 0;i <= mid;i++)q.push_back(v[0][i]);
if(ask(q, v[1]))hi = mid;
else lo = mid;
}
int x = v[0][hi];
lo = -1, hi = v[1].size();
while(hi - lo > 1){
int mid = (lo + hi) / 2;
vector<int> q;
for(int i = 0;i <= mid;i++)q.push_back(v[1][i]);
if(ask(q, v[0]))hi = mid;
else lo = mid;
}
int y = v[1][hi];
setRoad(x + 1, y + 1);
dsu.upd(x, y);
break;
}
}
}
}
// signed main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int t = 1;
// // cin>>t;
// while (t--)orz();
// }