| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 320611 | tasfiq4 | ICC (CEOI16_icc) | C++14 | 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 <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
int dsu[103];
vec grp[103];
int ara[103];
int find(int a)
{
if(dsu[a]==a) return a;
return dsu[a]=find(dsu[a]);
}
void uni(int x,int y)
{
int a,b,i,j;
a=find(x);
b=find(y);
if(grp[a].size()<grp[b].size()) swap(a,b);
dsu[b]=dsu[a];
ara[b]=1;
for(auto x:grp[b]) grp[a].pb(x);
}
pii operate(vec &g,vec &h)
{
if(g.size()==0 || h.size()==0) return {0,0};
int a[103],b[103],x,y,i,j;
fr(i,0,g.size()) a[i]=g[i];
fr(i,0,h.size()) b[i]=g[i];
int l=0,r=h.size();
if(!query(g.size(),a,h.size(),b)) return {0,0};
while(l+1<r)
{
int mid=(l+r)/2;
if(query(g.size(),a,mid,b))
{
r=mid;
}
else
{
l=mid;
}
}
x=r;
l=0,r=g.size();
while(l+1<r)
{
int mid=(l+r)/2;
if(query(mid,a,x,b))
{
r=mid;
}
else l=mid;
}
y=r;
return {a[y-1],b[x-1]};
}
void run(int n)
{
int i,j,k,a,b,c,x,y;
fr(i,1,n+1)
{
dsu[i]=i;
grp[i].pb(i);
}
fr(k,0,n-1)
{
fr(i,0,7)
{
vec g,h;
fr(j,1,n+1)
{
if(!ara[j])
{
if(j&(1<<i))
{
for(auto x:grp[j]) g.pb(x);
}
else
{
for(auto x:grp[j]) h.pb(x);
}
}
}
pii z=operate(g,h);
if(z.ft==0) continue;
else
{
uni(z.ft,z.sd);
setRoad(z.ft,z.sd);
break;
}
}
}
}