Submission #119955

#	Time	Username	Problem	Language	Result	Execution time	Memory
119955		faustaadp	ČVENK (COI15_cvenk)	C++17	100 / 100	2493 ms	411836 KiB

cvenk

#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 (stderr)

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++)
           ~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40