| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56316 |
2018-07-11T04:53:37 Z |
Yehezkiel |
ICC (CEOI16_icc) |
C++11 |
|
218 ms |
964 KB |
#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 print(vector <int> arr){
cout<<"printing arr"<<endl;
for(int i=0;i<(int) 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;
assert(isi==par[isi]);
}
vec.clear();
for(int i=1;i<=n;i++)
if(root[finds(i)])
vec.pb(i);
}
void shrink(vector <int> &vec){
int n=0;
for(int i=0;i<(int) vec.size();i++)
{
if(par[vec[i]]==vec[i])
vec[n++]=vec[i];
}
vec.resize(n);
}
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);
//cout<<"kuerinya "<<kueri<<endl;
lebih/=2;
//cout<<totalnya "<<total<<endl;
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);
return 0;
}
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<(int) 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;
vector <int> 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);
}
//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<(int) baru.size();i++)
{
for(auto isi:baru[i])
{
if(i&1)
kanan.pb(isi);
else
kiri.pb(isi);
}
}
assert(lebih==0);
assert(abs((int) kiri.size() - (int) kanan.size())<=1);
expand(kiri),expand(kanan);
if(tanya(kiri,kanan))
break;
anggota=baru;
}
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();
//cout<<"found"<<endl;
pii ans;
ans.fi=perkecil(kiri,kanan);
//sort(all(kanan));
//print(kanan);
kanan=possible[finds(ans.fi)];
expand(kanan);
//sort(all(kanan));
//print(kanan);
ans.se=perkecil(kanan,kiri);
setRoad(ans.fi,ans.se);
gabung(ans.fi,ans.se);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 95 queries used. |
| 2 |
Correct |
8 ms |
612 KB |
Ok! 94 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
688 KB |
Ok! 512 queries used. |
| 2 |
Correct |
47 ms |
688 KB |
Ok! 523 queries used. |
| 3 |
Correct |
56 ms |
720 KB |
Ok! 554 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
720 KB |
Ok! 1296 queries used. |
| 2 |
Correct |
180 ms |
736 KB |
Ok! 1220 queries used. |
| 3 |
Correct |
189 ms |
904 KB |
Ok! 1312 queries used. |
| 4 |
Correct |
208 ms |
904 KB |
Ok! 1302 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
904 KB |
Ok! 1305 queries used. |
| 2 |
Correct |
162 ms |
904 KB |
Ok! 1327 queries used. |
| 3 |
Correct |
184 ms |
904 KB |
Ok! 1320 queries used. |
| 4 |
Correct |
194 ms |
964 KB |
Ok! 1317 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
964 KB |
Ok! 1298 queries used. |
| 2 |
Correct |
150 ms |
964 KB |
Ok! 1332 queries used. |
| 3 |
Correct |
218 ms |
964 KB |
Ok! 1320 queries used. |
| 4 |
Correct |
150 ms |
964 KB |
Ok! 1340 queries used. |
| 5 |
Correct |
139 ms |
964 KB |
Ok! 1303 queries used. |
| 6 |
Correct |
164 ms |
964 KB |
Ok! 1344 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
964 KB |
Ok! 1334 queries used. |
| 2 |
Correct |
167 ms |
964 KB |
Ok! 1273 queries used. |
