Submission #140697

#	Time	Username	Problem	Language	Result	Execution time	Memory
140697		tmwilliamlin168	Ideal city (IOI12_city)	C++14	100 / 100	89 ms	10208 KiB

city

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

#define ll long long

const int mxN=1e5, M=1e9;
array<int, 2> a[mxN];
int n, c[mxN], d[mxN], s[mxN];
vector<int> adj[mxN];
ll ans;

ll dfs1(int u=0, int p=-1) {
	ll t=0;
	for(int v : adj[u]) {
		if(v==p)
			continue;
		t+=dfs1(v, u);
		s[u]+=s[v];
	}
	return t+s[u];
}

void dfs2(ll t, int u=0, int p=-1) {
	ans+=t*d[u];
	for(int v : adj[u])
		if(v^p)
			dfs2(t+n-2*s[v], v, u);
}

void solve(int *x, int *y) {
	for(int i=0; i<n; ++i)
		a[i]={x[i], y[i]};
	sort(a, a+n);
	int m=0;
	for(int i=0, j=0; i<n; i=j, ++m) {
		for(c[j++]=m; j<n&&a[j][0]==a[j-1][0]&&a[j][1]==a[j-1][1]+1; c[j++]=m);
		d[m]=s[m]=j-i;
	}
	for(int i=0; i<n; ++i) {
		int p=lower_bound(a, a+n, array<int, 2>{a[i][0]+1, a[i][1]})-a;
		if(p<n&&a[p][0]==a[i][0]+1&&a[p][1]==a[i][1]) {
			adj[c[i]].push_back(c[p]);
			adj[c[p]].push_back(c[i]);
		}
	}
	for(int i=0; i<m; ++i) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
	}
	dfs2(dfs1()-n);
}

int DistanceSum(int N, int *x, int *y) {
	n=N;
	solve(x, y);
	for(int i=0; i<n; ++i)
		adj[i].clear();
	solve(y, x);
	return ans/2%M;
}

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