| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 119955 |
2019-06-22T17:42:02 Z |
faustaadp |
ČVENK (COI15_cvenk) |
C++17 |
|
2493 ms |
411836 KB |
#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 za[3010101];
ll X[3010101];
ll Y[3010101];
unordered_map<ll,unordered_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]++;
ll vs=1;
za[0]=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[vs]=Z;
vs++;
//if(p[tem])continue;
}
for(j=1;j<vs;j++)
{
if(p[za[j-1]])break;
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";
}
Compilation message
cvenk.cpp: In function 'void dfs(ll, ll, ll)':
cvenk.cpp:23: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:34: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:81:7: warning: unused variable 'tem' [-Wunused-variable]
ll tem=Z;
^~~
cvenk.cpp:116:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1;j<ki.size();j++)
~^~~~~~~~~~
cvenk.cpp:121:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1;j<ka.size();j++)
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
212476 KB |
Output is correct |
| 2 |
Correct |
182 ms |
212404 KB |
Output is correct |
| 3 |
Correct |
181 ms |
212404 KB |
Output is correct |
| 4 |
Correct |
184 ms |
212412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
212676 KB |
Output is correct |
| 2 |
Correct |
179 ms |
212712 KB |
Output is correct |
| 3 |
Correct |
183 ms |
212576 KB |
Output is correct |
| 4 |
Correct |
175 ms |
212604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
213648 KB |
Output is correct |
| 2 |
Correct |
258 ms |
213428 KB |
Output is correct |
| 3 |
Correct |
223 ms |
212624 KB |
Output is correct |
| 4 |
Correct |
220 ms |
212616 KB |
Output is correct |
| 5 |
Correct |
229 ms |
212956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2444 ms |
411656 KB |
Output is correct |
| 2 |
Correct |
2493 ms |
411836 KB |
Output is correct |
| 3 |
Correct |
1490 ms |
333304 KB |
Output is correct |
| 4 |
Correct |
1329 ms |
315652 KB |
Output is correct |
| 5 |
Correct |
1382 ms |
315624 KB |
Output is correct |
