Submission #15624

#	Time	Username	Problem	Language	Result	Execution time	Memory
15624		progressive	Ideal city (IOI12_city)	C++14	100 / 100	81 ms	14460 KiB

city

#include<algorithm>
#include<vector>
using namespace std;
static const int MOD=1e9;
static const int MAXN=1e5+7;
static vector<int> connX[MAXN];
static vector<int> connY[MAXN];
static pair<pair<int,int>,int> Xsort[MAXN];
static pair<pair<int,int>,int> Ysort[MAXN];
static int Xgraph[MAXN];
static int Ygraph[MAXN];
static int Xweight[MAXN];
static int Yweight[MAXN];
static int Xtp=0;
static int Ytp=0;
static long long ans=0;
#include<cstdio>
static int N;
int dfsX(int a,int pa)
{
	int subtreesize=Xweight[a];
	for(int i=0;i<connX[a].size();i++)
	{
		if(connX[a][i]==pa) continue;
		int st=dfsX(connX[a][i],a);
		subtreesize+=st;
		ans+=1LL*st*(N-st);
	}
	return subtreesize;
}
int dfsY(int a,int pa)
{
	int subtreesize=Yweight[a];
	for(int i=0;i<connY[a].size();i++)
	{
		if(connY[a][i]==pa) continue;
		int st=dfsY(connY[a][i],a);
		subtreesize+=st;
		ans+=1LL*st*(N-st);
	}
	return subtreesize;
}

int DistanceSum(int N, int *X, int *Y) {
	::N=N;
	for(int i=0;i<N;i++) Xsort[i]=make_pair(make_pair(X[i],Y[i]),i);
	for(int i=0;i<N;i++) Ysort[i]=make_pair(make_pair(Y[i],X[i]),i);
	sort(Xsort,Xsort+N);
	sort(Ysort,Ysort+N);
	for(int i=0;i<N;i++)
	{
		if(
		i!=0 && 
		Xsort[i-1].first.first==Xsort[i].first.first &&
		Xsort[i-1].first.second+1 == Xsort[i].first.second )
		Xtp--;
		Xweight[Xtp]++;
		Xgraph[Xsort[i].second]=Xtp++;
	}
	for(int i=0;i<N;i++)
	{
		if(
		i!=0 && 
		Ysort[i-1].first.first==Ysort[i].first.first &&
		Ysort[i-1].first.second+1 == Ysort[i].first.second )
		Ytp--;
		Yweight[Ytp]++;
		Ygraph[Ysort[i].second]=Ytp++;
	}
	for(int i=0;i<N-1;i++)
	{
		
		int A=Ygraph[Xsort[i].second], B=Ygraph[Xsort[i+1].second];
		int C=Xgraph[Ysort[i].second], D=Xgraph[Ysort[i+1].second];
		if(Xsort[i].first.first==Xsort[i+1].first.first && Xsort[i].first.second+1==Xsort[i+1].first.second)
		{
			connY[A].push_back(B);
			connY[B].push_back(A);
		}
		if(Ysort[i].first.first==Ysort[i+1].first.first && Ysort[i].first.second+1==Ysort[i+1].first.second)
		{
			connX[C].push_back(D);
			connX[D].push_back(C);
		}
	}
	for(int i=0;i<Xtp;i++)
	{
		sort(connX[i].begin(),connX[i].end());
		connX[i].resize(unique(connX[i].begin(),connX[i].end())-connX[i].begin());
	}
	for(int i=0;i<Ytp;i++)
	{
		sort(connY[i].begin(),connY[i].end());
		connY[i].resize(unique(connY[i].begin(),connY[i].end())-connY[i].begin());
	}
	dfsX(0,-1);
	dfsY(0,-1);
	return ans%MOD;
	
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45