Submission #159582

#	Time	Username	Problem	Language	Result	Execution time	Memory
159582		arnold518	Ideal city (IOI12_city)	C++14	100 / 100	91 ms	35408 KiB

city

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll MOD = 1e9;

struct Point
{
    int x, y;
};

int N;
ll ans;
Point A[MAXN+10];
vector<int> point1[MAXN+10];
vector<int> l1[MAXN+10], r1[MAXN+10], k1[MAXN+10];
vector<int> adj1[MAXN+10];

vector<int> point2[MAXN+10];
vector<int> l2[MAXN+10], r2[MAXN+10], k2[MAXN+10];
vector<int> adj2[MAXN+10];

ll sz[MAXN+10], sum[MAXN+10], val[MAXN+10];

void dfs(int now, int bef, int depth, vector<int> *adj)
{
	sum[now]=depth*val[now];
	sz[now]=val[now];
/*
	printf("%d : ", now);
	for(int nxt : adj[now]) printf("%d ", nxt);
	printf("\n");
*/

	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, depth+1, adj);
		sum[now]+=sum[nxt];
		sz[now]+=sz[nxt];
	}

	//printf("%d %d %lld %lld\n", now, depth, sz[now], sum[now]);

	ll x=0;
	x+=sum[now]-depth*sz[now];
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		x+=(sum[nxt]-depth*sz[nxt])*(sz[now]-sz[nxt]-1);
		x%=MOD;
	}
	//printf("%lld\n", x);
	ans+=x;
	ans%=MOD;
}

int DistanceSum(int _N, int *X, int *Y)
{
    int i, j, k;
    N=_N;
    for(i=1; i<=N; i++) A[i]={X[i-1], Y[i-1]};

    int minx=2147483647, miny=2147483647;
	for(i=1; i<=N; i++) minx=min(minx, A[i].x);
	for(i=1; i<=N; i++) miny=min(miny, A[i].y);
	minx--; miny--;

	for(i=1; i<=N; i++) A[i].x-=minx, A[i].y-=miny;

	for(i=1; i<=N; i++) point1[A[i].x].push_back(A[i].y);
	int cnt=1;
	for(i=1; i<=N; i++)
	{
		if(point1[i].empty()) break;
		sort(point1[i].begin(), point1[i].end());

		l1[i].push_back(point1[i][0]);
		k1[i].push_back(cnt++);
		for(j=1; j<point1[i].size(); j++)
		{
			int x=point1[i][j-1], y=point1[i][j];
			if(x+1<y)
			{
				r1[i].push_back(x);
				val[k1[i].back()]=r1[i].back()-l1[i].back()+1;
				l1[i].push_back(y);
				k1[i].push_back(cnt++);
			}
		}
		r1[i].push_back(point1[i].back());
		val[k1[i].back()]=r1[i].back()-l1[i].back()+1;
	}

	for(i=2; i<=N; i++)
	{
		if(point1[i].empty()) break;
		for(j=0; j<l1[i].size(); j++)
		{
			int p=lower_bound(r1[i-1].begin(), r1[i-1].end(), l1[i][j])-r1[i-1].begin();
			int q=upper_bound(l1[i-1].begin(), l1[i-1].end(), r1[i][j])-l1[i-1].begin();
			for(k=p; k<q; k++) adj1[k1[i][j]].push_back(k1[i-1][k]), adj1[k1[i-1][k]].push_back(k1[i][j]);
		}
	}

	dfs(1, 1, 0, adj1);

	//printf("======================\n");

	for(i=1; i<=N; i++) point2[A[i].y].push_back(A[i].x);
	cnt=1;
	for(i=1; i<=N; i++)
	{
		if(point2[i].empty()) break;
		sort(point2[i].begin(), point2[i].end());

		l2[i].push_back(point2[i][0]);
		k2[i].push_back(cnt++);
		for(j=1; j<point2[i].size(); j++)
		{
			int x=point2[i][j-1], y=point2[i][j];
			if(x+1<y)
			{
				r2[i].push_back(x);
				val[k2[i].back()]=r2[i].back()-l2[i].back()+1;
				l2[i].push_back(y);
				k2[i].push_back(cnt++);
			}
		}
		r2[i].push_back(point2[i].back());
		val[k2[i].back()]=r2[i].back()-l2[i].back()+1;
	}

	for(i=2; i<=N; i++)
	{
		if(point2[i].empty()) break;
		for(j=0; j<l2[i].size(); j++)
		{
			int p=lower_bound(r2[i-1].begin(), r2[i-1].end(), l2[i][j])-r2[i-1].begin();
			int q=upper_bound(l2[i-1].begin(), l2[i-1].end(), r2[i][j])-l2[i-1].begin();
			for(k=p; k<q; k++) adj2[k2[i][j]].push_back(k2[i-1][k]), adj2[k2[i-1][k]].push_back(k2[i][j]);
		}
	}

	dfs(1, 1, 0, adj2);

	return ans;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<point1[i].size(); j++)
            ~^~~~~~~~~~~~~~~~~
city.cpp:102:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<l1[i].size(); j++)
            ~^~~~~~~~~~~~~
city.cpp:123:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<point2[i].size(); j++)
            ~^~~~~~~~~~~~~~~~~
city.cpp:141:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<l2[i].size(); j++)
            ~^~~~~~~~~~~~~

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