oj.uz

Submission #13543

# Submission time Handle Problem Language Result Execution time Memory
13543 2015-02-23T12:50:31 Z ainta Ideal city (IOI12_city) C++
100 / 100
 88 ms 12688 KB 
#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.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9704 KB Output is correct
2 Correct 15 ms 9704 KB Output is correct
3 Correct 31 ms 10020 KB Output is correct
4 Correct 31 ms 10020 KB Output is correct
5 Correct 71 ms 10412 KB Output is correct
6 Correct 72 ms 10412 KB Output is correct
7 Correct 67 ms 10412 KB Output is correct
8 Correct 71 ms 10412 KB Output is correct
9 Correct 60 ms 10440 KB Output is correct
10 Correct 68 ms 12688 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9968 KB Output is correct
2 Correct 10 ms 9836 KB Output is correct
3 Correct 44 ms 10548 KB Output is correct
4 Correct 36 ms 10284 KB Output is correct
5 Correct 84 ms 11600 KB Output is correct
6 Correct 78 ms 10860 KB Output is correct
7 Correct 88 ms 11640 KB Output is correct
8 Correct 65 ms 10808 KB Output is correct
9 Correct 69 ms 10676 KB Output is correct
10 Correct 74 ms 10676 KB Output is correct