oj.uz

Submission #197022

# Submission time Handle Problem Language Result Execution time Memory
197022 2020-01-18T06:55:23 Z ainta Ideal city (IOI12_city) C++17
100 / 100
 88 ms 10044 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];
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pp){
			DFS(E[a][i], a);
			C[a] += C[E[a][i]];
		}
	}
    Res += C[a] * (n-C[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);
	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%1000000000;
}

Compilation message

city.cpp: In function 'void DFS(int, int)':
city.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~
city.cpp: In function 'void Do()':
city.cpp:26:24: warning: unused variable 'j' [-Wunused-variable]
  int i, cnt = 0, a, b, j, cc = 0;
                        ^

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 10 ms 2936 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3576 KB Output is correct
2 Correct 16 ms 3576 KB Output is correct
3 Correct 35 ms 4824 KB Output is correct
4 Correct 36 ms 4860 KB Output is correct
5 Correct 69 ms 6852 KB Output is correct
6 Correct 69 ms 6776 KB Output is correct
7 Correct 69 ms 7032 KB Output is correct
8 Correct 69 ms 6724 KB Output is correct
9 Correct 69 ms 7032 KB Output is correct
10 Correct 70 ms 10044 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4088 KB Output is correct
2 Correct 18 ms 3960 KB Output is correct
3 Correct 44 ms 6008 KB Output is correct
4 Correct 40 ms 5496 KB Output is correct
5 Correct 86 ms 9080 KB Output is correct
6 Correct 75 ms 7772 KB Output is correct
7 Correct 88 ms 9336 KB Output is correct
8 Correct 76 ms 7756 KB Output is correct
9 Correct 74 ms 7544 KB Output is correct
10 Correct 74 ms 7568 KB Output is correct