| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 119953 | faustaadp | ČVENK (COI15_cvenk) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,j,ta,tb,has,hz,n,te;
ll bes[3010101];
ll p[3010101];
ll X[3010101];
ll Y[3010101];
unordered_map<ll,unodrered_map<ll,ll> > me;
vector<ll> v[3010101];
vector<ll> w[3010101];
vector<ll> ank[3010101];
void dfs(ll aa,ll bb,ll cc)
{
ll ii;
// cout<<aa<<" "<<bb<<"\n";
hz+=cc*bes[aa];
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
{
dfs(v[aa][ii],aa,cc+w[aa][ii]);
bes[aa]+=bes[v[aa][ii]];
}
}
void dfs2(ll aa,ll bb,ll cc)
{
ll ii;
has=min(has,cc);
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
{
ll tom=-bes[v[aa][ii]]-bes[v[aa][ii]]+n;
tom*=w[aa][ii];
dfs2(v[aa][ii],aa,cc+tom);
}
}
ll buat(ll aa,ll bb)
{
if(me[aa][bb]==0)
{
me[aa][bb]=++te;
X[te]=aa;
Y[te]=bb;
}
return me[aa][bb];
}
void capar(ll &aa,ll &bb)
{
ll ii;
for(ii=0;ii<=30;ii++)
if((aa|bb)&(1<<ii))
{
if(aa&(1<<ii))
aa^=(1<<ii);
else
bb^=(1<<ii);
break;
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
buat(0,0);
for(i=1;i<=n;i++)
{
cin>>ta>>tb;
ll Z=buat(ta,tb);
bes[Z]++;
vector<ll> za;
ll vs=1;
za.pb(Z);
//cout<<Z<<"\n";
while(Z!=1)
{
capar(ta,tb);
ll tem=Z;
// cout<<ta<<" "<<tb<<"\n";
Z=buat(ta,tb);
while(vs>=2&&((X[za[vs-1]]==X[za[vs-2]]&&X[za[vs-1]]==X[Z])||(Y[za[vs-1]]==Y[za[vs-2]]&&Y[za[vs-1]]==Y[Z])))
{
vs--;
za.pop_back();
}
vs++;
za.pb(Z);
//if(p[tem])continue;
}
for(j=1;j<za.size();j++)
{
if(p[za[j-1]])continue;
p[za[j-1]]=za[j];
ank[za[j]].pb(za[j-1]);
}
}
for(i=1;i<=te;i++)
{
sort(ank[i].begin(),ank[i].end());
ll sz=ank[i].size();
vector<pair<ll,ll> > ki,ka;
ki.pb(mp(Y[i],i));
ka.pb(mp(X[i],i));
for(j=0;j<sz;j++)
{
//cout<<X[i]<<" "<<Y[i]<<" -> "<<X[ank[i][j]]<<" "<<Y[ank[i][j]]<<"\n";
if(X[ank[i][j]]==X[i])
ki.pb(mp(Y[ank[i][j]],ank[i][j]));
else
ka.pb(mp(X[ank[i][j]],ank[i][j]));
}
sort(ki.begin(),ki.end());
sort(ka.begin(),ka.end());
for(j=1;j<ki.size();j++)
{
v[ki[j-1].se].pb(ki[j].se);
w[ki[j-1].se].pb(ki[j].fi-ki[j-1].fi);
}
for(j=1;j<ka.size();j++)
{
v[ka[j-1].se].pb(ka[j].se);
w[ka[j-1].se].pb(ka[j].fi-ka[j-1].fi);
}
}
// for(i=1;i<=te;i++)
// for(j=0;j<v[i].size();j++)
// cout<<X[i]<<" "<<Y[i]<<" "<<X[v[i][j]]<<" "<<Y[v[i][j]]<<" "<<w[i][j]<<"\n";
//return 0;
has=1e18;
dfs(1,1,0);
//cout<<hz<<"\n";
dfs2(1,1,hz);
cout<<has<<"\n";
}