| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 812599 | 2023-08-07T09:29:17 Z | TheSahib | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define ll long long
#define oo 1e9
#define pii pair<int, int>
using namespace std;
const int MAX = 105;
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
int n;
set<int> comps;
int par[MAX];
vector<int> st[MAX];
int get(int node){
if(par[node] < 0) return node;
return par[node] = get(par[node]);
}
int unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return false;
if(-par[a] < -par[b]) swap(a, b);
for(int c:st[b]){
st[a].push_back(c);
}
par[a] += par[b];
par[b] = a;
comps.erase(b);
return false;
}
bool queryComp(vector<int> a, vector<int> b){
vector<int> tmp1, tmp2;
for(int c:a){
for(int x:st[c]){
tmp1.push_back(x);
}
}
for(int c:b){
for(int x:st[c]){
tmp2.push_back(x);
}
}
return query(a.size(), b.size(), a.data(), b.data());
}
void f(vector<int>& a, vector<int>& b){
if(a.size() == 1 && b.size() == 1) return;
int l = 0, r = a.size() - 1;
while(l < r){
int mid = (l + r) / 2;
vector<int> tmp;
for(int i = l; i <= mid; ++i){
tmp.push_back(a[i]);
}
if(query(tmp.size(), b.size(), tmp.data(), b.data())){
r = mid;
}
else{
l = mid + 1;
}
}
int c = a[l];
a.clear();
a.push_back(c);
if(b.size() != 1){
f(b, a);
}
}
void run(int N){
n = N;
for (int i = 0; i < n; i++)
{
par[i] = -1;
st[i].push_back(i);
comps.insert(i);
}
for (int k = 0; k < N - 1; k++)
{
vector<int> v;
for(int a:comps){
v.push_back(a);
}
vector<int> v1, v2;
while(true){
random_shuffle(v.begin(), v.end());
int mid = (v.size() - 1) / 2;
vector<int> tmp1, tmp2;
for(int i = 0; i < v.size(); ++i){
if(i <= mid){
tmp1.push_back(v[i]);
}
else{
tmp2.push_back(v[i]);
}
}
if(queryComp(tmp1, tmp2)){
for(int c:tmp1){
for(int x:st[c]){
v1.push_back(x);
}
}
for(int c:tmp2){
for(int x:st[c]){
v2.push_back(x);
}
}
break;
}
}
f(v1, v2);
setRoad(v1[0], v2[0]);
unite(v1[0], v2[0]);
}
}