| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 56286 | Yehezkiel | ICC (CEOI16_icc) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
const int MAXN=100;
int par[MAXN+5],n;
int finds(int x){
if(par[x]!=x)
par[x]=finds(par[x]);
return par[x];
}
bool connected(int u,int v){
return (finds(u)==finds(v));
}
void gabung(int u,int v){
u=finds(u),v=finds(v);
if(u==v)
return;
par[v]=u;
}
int tanya(vector <int> a,vector <int> b){ //O(N)
int arr1[105];int arr2[105];
for(int i=0;i<a.size();i++)
arr1[i]=a[i];
for(int i=0;i<b.size();i++)
arr2[i]=b[i];
return query(a.size(),b.size(),arr1,arr2);
}
void print(vector <int> arr){
cout<<"printing arr"<<endl;
for(int i=0;i<arr.size();i++)
cout<<arr[i]<<" ";
cout<<endl;
}
void expand(vector <int> &vec){ //isinya cuman kepala suku O(N)
bool root[MAXN+5];
for(int i=1;i<=n;i++)
root[i]=false;
for(auto isi:vec)
root[isi]=true;
vec.clear();
for(int i=1;i<=n;i++)
if(root[finds(i)])
vec.pb(i);
}
void perkecil(vector <int> &now,const vector <int> &other){ //O(NlogN)
vector <int> temp;
while(now.size()>1) //O(logN)
{
random_shuffle(now);
temp.clear();
for(int i=now.size()/2;i<now.size();i++)
temp.pb(now[i]);
now.resize(now.size()/2);
if(tanya(now,other)==0) //O(N)
now=temp;
}
}
void bagiDua(vector <int> &vec,int &lebih,vector<vector<int> > &tampung){
random_shuffle(all(vec));
int ambil=vec.size()/2;
if(lebih&&(vec.size()&1))
lebih--,ambil++;
vector <int> kiri,kanan;
for(int i=0;i<vec.size();i++)
{
if(i<ambil)
kiri.pb(vec[i]);
else
kanan.pb(vec[i]);
}
tampung.pb(kiri);tampung.pb(kanan);
}
vector <int> kiri,kanan;
void findAnggota(){
vector <vector <int> > anggota,baru;
anggota.resize(1);
for(int i=1;i<=n;i++)
{
if(par[i]==i)
anggota[0].pb(i);
}
//cout<<"MULAI"<<endl;
for(int loop=0;;loop++)
{
baru.clear();
int lebih=0;
for(auto &isi:anggota)
lebih+=isi.size()%2;
lebih/=2;
int terbesar=-1;
for(auto &isi:anggota)
{
terbesar=max(terbesar,(int) isi.size());
bagiDua(isi,lebih,baru);
}
assert(terbesar>1);
kiri.clear();kanan.clear();
for(int i=0;i<baru.size();i++)
{
for(auto isi:baru[i])
{
if(i&1)
kanan.pb(isi);
else
kiri.pb(isi);
}
}
assert(lebih==0);
//cout<<loop<<" "<<target<<" "<<(ukuran<<loop)<<" "<<lebih<<endl;
//cout<<kiri.size()<<" "<<kanan.size()<<endl;
assert(abs((int) kiri.size() - (int) kanan.size())<=1);
expand(kiri),expand(kanan);
if(tanya(kiri,kanan))
break;
anggota=baru;
}
}
void run(int _n){
srand(0);
n=_n;
for(int i=1;i<=n;i++)
par[i]=i;
for(int i=0;i<n-1;i++)
{
findAnggota();
perkecil(kiri,kanan);
perkecil(kanan,kiri);
setRoad(kiri[0],kanan[0]);
gabung(kiri[0],kanan[0]);
}
}