oj.uz

Submission #15624

# Submission time Handle Problem Language Result Execution time Memory
15624 2015-07-13T11:49:03 Z progressive Ideal city (IOI12_city) C++14
100 / 100
 81 ms 14460 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10172 KB Output is correct
2 Correct 0 ms 10172 KB Output is correct
3 Correct 0 ms 10172 KB Output is correct
4 Correct 3 ms 10304 KB Output is correct
5 Correct 3 ms 10304 KB Output is correct
6 Correct 3 ms 10304 KB Output is correct
7 Correct 0 ms 10304 KB Output is correct
8 Correct 3 ms 10304 KB Output is correct
9 Correct 0 ms 10304 KB Output is correct
10 Correct 0 ms 10304 KB Output is correct
11 Correct 0 ms 10304 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10304 KB Output is correct
2 Correct 3 ms 10304 KB Output is correct
3 Correct 4 ms 10308 KB Output is correct
4 Correct 4 ms 10308 KB Output is correct
5 Correct 0 ms 10308 KB Output is correct
6 Correct 2 ms 10308 KB Output is correct
7 Correct 4 ms 10308 KB Output is correct
8 Correct 4 ms 10308 KB Output is correct
9 Correct 4 ms 10308 KB Output is correct
10 Correct 0 ms 10308 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10908 KB Output is correct
2 Correct 12 ms 10912 KB Output is correct
3 Correct 31 ms 11752 KB Output is correct
4 Correct 28 ms 11624 KB Output is correct
5 Correct 53 ms 13728 KB Output is correct
6 Correct 64 ms 13532 KB Output is correct
7 Correct 66 ms 13200 KB Output is correct
8 Correct 46 ms 13600 KB Output is correct
9 Correct 60 ms 12904 KB Output is correct
10 Correct 55 ms 14460 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10908 KB Output is correct
2 Correct 17 ms 10908 KB Output is correct
3 Correct 40 ms 12016 KB Output is correct
4 Correct 36 ms 11884 KB Output is correct
5 Correct 78 ms 13728 KB Output is correct
6 Correct 71 ms 13384 KB Output is correct
7 Correct 81 ms 13896 KB Output is correct
8 Correct 68 ms 13332 KB Output is correct
9 Correct 70 ms 13332 KB Output is correct
10 Correct 66 ms 13332 KB Output is correct