| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56374 |
2018-07-11T07:35:56 Z |
Yehezkiel |
ICC (CEOI16_icc) |
C++11 |
|
226 ms |
876 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){
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){ //vec is only filled with the head of components, we want to find the whole components
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);
}
void perkecil(vector <int> &now,const vector <int> &other){ //Query(now,other) is 1, we only need to find the right "now"
vector <int> temp;
while(now.size()>1) //O(logN)
{
temp.clear();
for(int i=now.size()/2;i<(int) now.size();i++)
temp.pb(now[i]);
now.resize(now.size()/2);
if(tanya(now,other)==0) //O(N)
now=temp;
}
//when only one possibility exist, it must be the right now
}
void bagiDua(vector <int> &vec,int &lebih,vector<vector<int> > &tampung){
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) //the head of component
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){
n=_n;
for(int i=1;i<=n;i++)
par[i]=i;
for(int i=0;i<n-1;i++)
{
findAnggota();
perkecil(kiri,kanan);
kanan=possible[finds(kiri[0])];
expand(kanan);
perkecil(kanan,kiri);
setRoad(kiri[0],kanan[0]);
gabung(kiri[0],kanan[0]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 96 queries used. |
| 2 |
Correct |
13 ms |
656 KB |
Ok! 96 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
692 KB |
Ok! 506 queries used. |
| 2 |
Correct |
51 ms |
692 KB |
Ok! 641 queries used. |
| 3 |
Correct |
57 ms |
804 KB |
Ok! 636 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
816 KB |
Ok! 1395 queries used. |
| 2 |
Correct |
191 ms |
816 KB |
Ok! 1607 queries used. |
| 3 |
Correct |
170 ms |
816 KB |
Ok! 1556 queries used. |
| 4 |
Correct |
152 ms |
816 KB |
Ok! 1396 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
876 KB |
Ok! 1496 queries used. |
| 2 |
Correct |
158 ms |
876 KB |
Ok! 1480 queries used. |
| 3 |
Correct |
153 ms |
876 KB |
Ok! 1607 queries used. |
| 4 |
Correct |
151 ms |
876 KB |
Ok! 1361 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
876 KB |
Ok! 1600 queries used. |
| 2 |
Correct |
168 ms |
876 KB |
Ok! 1602 queries used. |
| 3 |
Correct |
165 ms |
876 KB |
Ok! 1596 queries used. |
| 4 |
Correct |
163 ms |
876 KB |
Ok! 1586 queries used. |
| 5 |
Correct |
154 ms |
876 KB |
Ok! 1469 queries used. |
| 6 |
Correct |
159 ms |
876 KB |
Ok! 1492 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
876 KB |
Ok! 1602 queries used. |
| 2 |
Correct |
184 ms |
876 KB |
Ok! 1607 queries used. |
