oj.uz

답안 #119954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119954 2019-06-22T17:37:17 Z faustaadp ČVENK (COI15_cvenk) C++17
100 / 100
 2541 ms 414148 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 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]++;
		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";
}

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:81:7: warning: unused variable 'tem' [-Wunused-variable]
    ll tem=Z;
       ^~~
cvenk.cpp:93:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<za.size();j++)
           ~^~~~~~~~~~
cvenk.cpp:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<ki.size();j++)
           ~^~~~~~~~~~
cvenk.cpp:122:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<ka.size();j++)
           ~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 212408 KB Output is correct
2 Correct 182 ms 212428 KB Output is correct
3 Correct 209 ms 212424 KB Output is correct
4 Correct 188 ms 212488 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 212768 KB Output is correct
2 Correct 178 ms 212640 KB Output is correct
3 Correct 182 ms 212684 KB Output is correct
4 Correct 174 ms 212632 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 213360 KB Output is correct
2 Correct 278 ms 213376 KB Output is correct
3 Correct 255 ms 212588 KB Output is correct
4 Correct 228 ms 212528 KB Output is correct
5 Correct 234 ms 212848 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2525 ms 412276 KB Output is correct
2 Correct 2541 ms 414148 KB Output is correct
3 Correct 1534 ms 334360 KB Output is correct
4 Correct 1304 ms 316656 KB Output is correct
5 Correct 1400 ms 316544 KB Output is correct