#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];
map<ll,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]++;
//cout<<Z<<"\n";
while(Z!=1)
{
capar(ta,tb);
ll tem=Z;
// cout<<ta<<" "<<tb<<"\n";
Z=buat(ta,tb);
if(p[tem])break;
p[tem]=Z;
ank[Z].pb(tem);
}
}
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";
}
Compilation message
cvenk.cpp: In function 'void dfs(ll, ll, ll)':
cvenk.cpp:22:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
cvenk.cpp: In function 'void dfs2(ll, ll, ll)':
cvenk.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:103:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1;j<ki.size();j++)
~^~~~~~~~~~
cvenk.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1;j<ka.size();j++)
~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
173 ms |
212412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
181 ms |
212960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
245 ms |
214104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2821 ms |
488956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
