Submission #56361

#TimeUsernameProblemLanguageResultExecution timeMemory
56361YehezkielICC (CEOI16_icc)C++11
100 / 100
174 ms880 KiB
#include "icc.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() typedef pair<int,int> pii; 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<(int) a.size();i++) arr1[i]=a[i]; for(int i=0;i<(int) b.size();i++) arr2[i]=b[i]; return query(a.size(),b.size(),arr1,arr2); } 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; assert(isi==par[isi]); } vec.clear(); for(int i=1;i<=n;i++) if(root[finds(i)]) vec.pb(i); } void masukkan(vector <int> &tampung,const vector <int> tambahan){ for(int isi:tambahan) tampung.pb(isi); } int perkecil(vector <int> now,const vector <int> other){ //O(NlogN) int nomor[MAXN+5],n=0; for(int i=0;i<(int) now.size();i++) { if(now[i]==par[now[i]]) nomor[now[i]]=n++; } vector <vector <int> > temp1,temp2; temp1.resize(n),temp2.resize(n); for(int i=0;i<(int) now.size();i++) temp1[nomor[finds(now[i])]].pb(now[i]); int kueri=0; while(true) //O(logN) { int total=0,lebih=0; for(int i=0;i<n;i++) { total+=temp1[i].size(); lebih+=temp1[i].size()%2; } if(total==1) break; kueri++; assert(kueri<=7); lebih/=2; now.clear(); for(int i=0;i<n;i++) { random_shuffle(all(temp1[i])); int ambil=temp1[i].size()/2; if(temp1[i].size()&1&&lebih) ambil++,lebih--; temp2[i].clear(); for(int j=ambil;j<(int) temp1[i].size();j++) temp2[i].pb(temp1[i][j]); temp1[i].resize(ambil); masukkan(now,temp1[i]); } assert(lebih==0); assert(abs( (int)now.size() - ( total - (int)now.size() ) )<=1); if(tanya(now,other)==0) //O(N) { for(int i=0;i<n;i++) temp1[i]=temp2[i]; } } for(int i=0;i<n;i++) { if(temp1[i].size()==1) return temp1[i][0]; } assert(false); } void bagiDua(vector <int> &vec,int &lebih,vector<vector<int> > &tampung){ random_shuffle(all(vec)); //Just for Optimization int ambil=vec.size()/2; if(lebih&&(vec.size()&1)) lebih--,ambil++; vector <int> kiri,kanan; for(int i=0;i<(int) vec.size();i++) (i<ambil)?kiri.pb(vec[i]):kanan.pb(vec[i]); tampung.pb(kiri);tampung.pb(kanan); } vector <int> kiri,kanan,possible[MAXN+5]; 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); } while(true) { baru.clear(); int lebih=0; //to Divide the odd element equally for(auto &isi:anggota) lebih+=isi.size()%2; lebih/=2; for(auto &isi:anggota) bagiDua(isi,lebih,baru); assert(lebih==0); kiri.clear();kanan.clear(); for(int i=0;i<(int) baru.size();i++) (i&1)?masukkan(kanan,baru[i]):masukkan(kiri,baru[i]); assert(abs((int) kiri.size() - (int) kanan.size())<=1); expand(kiri),expand(kanan); if(tanya(kiri,kanan)) break; anggota=baru; } //Find Possibility, For Optimization for(int i=0;i<(int) baru.size();i+=2) { assert(i+1<(int) baru.size()); for(auto isi:baru[i]) { possible[isi].clear(); masukkan(possible[isi],baru[i+1]); } } } void run(int _n){ srand(2305); n=_n; for(int i=1;i<=n;i++) par[i]=i; for(int i=0;i<n-1;i++) { findAnggota(); pii ans; ans.fi=perkecil(kiri,kanan); kanan=possible[finds(ans.fi)]; expand(kanan); ans.se=perkecil(kanan,kiri); setRoad(ans.fi,ans.se); gabung(ans.fi,ans.se); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...