Submission #13543

#	Time	Username	Problem	Language	Result	Execution time	Memory
13543		ainta	Ideal city (IOI12_city)	C++98	100 / 100	88 ms	12688 KiB

city

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000];
int n, SZ[101000], P[101000];
long long Res, D[101000], C[101000];
struct point{
	int x, y, num;
	bool operator<(const point &p)const{
		return x != p.x ? x < p.x : y < p.y;
	}
}w[101000], w2[101000], L[101000];
void DFS(int a, int pp){
	int i;
	C[a] = SZ[a];
	D[a] = 0;
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pp){
			DFS(E[a][i], a);
			C[a] += C[E[a][i]];
			D[a] += D[E[a][i]] + C[E[a][i]];
		}
	}
}
void DFS2(int a, int pp){
	int i;
	Res += D[a] * SZ[a];
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pp){
			D[E[a][i]] = D[a] + (C[1] - C[E[a][i]] * 2);
			DFS2(E[a][i], a);
		}
	}
}
void Do(){
	int i, cnt = 0, a, b, j, cc = 0;
	sort(w, w + n);
	for (i = 0; i < n; i++){
		if (!i || w[i].x != w[i - 1].x || w[i - 1].y + 1 != w[i].y)SZ[++cnt] = 0;
		SZ[cnt]++;
		w2[i].num = cnt, w2[i].x = w[i].y, w2[i].y = w[i].x;
	}
	for (i = 1; i <= cnt; i++)P[i] = 0;
	sort(w2, w2 + n);
	for (i = 0; i < n - 1; i++){
		if (w2[i].x == w2[i + 1].x && w2[i].y + 1 == w2[i + 1].y){
			a = w2[i].num, b = w2[i + 1].num;
			if (P[a] != b){
				P[a] = b;
				L[cc].x = a, L[cc].y = b; cc++;
			}
		}
	}
	for (i = 0; i < cc; i++){
		E[L[i].x].push_back(L[i].y);
		E[L[i].y].push_back(L[i].x);
	}
	DFS(1, 0);
	DFS2(1, 0);
	for (i = 1; i <= cnt; i++)E[i].clear();
}
int DistanceSum(int N, int *X, int *Y) {
	int i;
	n = N;
	for (i = 0; i < N; i++){
		w[i].x = X[i], w[i].y = Y[i];
	}
	Do();
	for (i = 0; i < N; i++){
		w[i].x = Y[i], w[i].y = X[i];
	}
	Do();
	return (Res/2)%1000000000;
}

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