oj.uz

Submission #469073

# Submission time Handle Problem Language Result Execution time Memory
469073 2021-08-30T15:45:40 Z ntabc05101 Ideal city (IOI12_city) C++14
100 / 100
 55 ms 7792 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9;

int N;
long long res;
vector< vector<int> > adj;
vector<int> w;

int dfs(int u, int p) {
	int W = w[u];
	for (auto &to: adj[u]) {
		if (to != p) {
			int v = dfs(to, u);
			(res += 1ll * v * (N - v)) %= mod;
			W += v;
		}
	}
	return W;
}
		
int DistanceSum(int N, int *X, int *Y) {
	::N = N;
	int mnX = (1LL << 31) - 2, mnY = mnX, mxX = 0, mxY = 0;
	for (int i = 0; i < N; i++) {
		mnX = min(mnX, X[i]);	mnY = min(mnY, Y[i]);
		mxX = max(mxX, X[i]); mxY = max(mxY, Y[i]);
	}
	mxX -= mnX - 1; mxY -= mnY - 1;
	for (int i = 0; i < N; i++) {
		X[i] -= mnX; Y[i] -= mnY;
	}
	
	res = 0;
	vector<int> c, d;
	vector< vector<int> > pts;
	for (int e = 0; e < 2; e++) {
		pts.assign(mxX, vector<int>());
		for (int i = 0; i < N; i++) {
			pts[X[i]].push_back(Y[i]);
		}
		int cur = 0, cnt = 0;
		w.clear(); c.clear(); d.clear();
		adj.clear();
		adj.push_back(vector<int>());
		for (int i = 0; i < mxX; i++) {
			sort(pts[i].begin(), pts[i].end());
			
			int k = 0;
			d.clear();
			for (int j = 0; j < pts[i].size(); j++) {
				d.push_back(cur);
				cnt++;
				if (i > 0) {
					while (k < pts[i - 1].size() && pts[i - 1][k] < pts[i][j]) {
						k++;
					}
					if (k < pts[i - 1].size() && pts[i - 1][k] == pts[i][j]) {
						adj[cur].push_back(c[k]);
						adj[c[k]].push_back(cur);
					}
				}
				if (j == pts[i].size() - 1 || pts[i][j] + 1 < pts[i][j + 1]) {
					w.push_back(cnt);
					cur++; cnt = 0;
					adj.push_back(vector<int>());
				}
			}
			swap(c, d);
		}
		
		for (auto& ad: adj) {
			sort(ad.begin(), ad.end());
			ad.resize(unique(ad.begin(), ad.end()) - ad.begin());
			/*for (auto& _: ad) {
				cout << _ << " ";
			}
			cout << "\n";*/
		}
		
		dfs(0, -1);
		
		for (int i = 0; i < N; i++) {
			swap(X[i], Y[i]);
		}
		swap(mxX, mxY);
	}
	
	return res;
}

/*int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);	
	
  int N; cin >> N;
	int *X = new int[N], *Y = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
	}
	
	cout << DistanceSum(N, X, Y) << "\n";

	return 0;
}*/

/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for (int j = 0; j < pts[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
city.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |      while (k < pts[i - 1].size() && pts[i - 1][k] < pts[i][j]) {
      |             ~~^~~~~~~~~~~~~~~~~~~
city.cpp:59:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |      if (k < pts[i - 1].size() && pts[i - 1][k] == pts[i][j]) {
      |          ~~^~~~~~~~~~~~~~~~~~~
city.cpp:64:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if (j == pts[i].size() - 1 || pts[i][j] + 1 < pts[i][j + 1]) {
      |         ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 844 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 21 ms 1944 KB Output is correct
4 Correct 20 ms 2124 KB Output is correct
5 Correct 42 ms 3956 KB Output is correct
6 Correct 41 ms 4136 KB Output is correct
7 Correct 54 ms 3880 KB Output is correct
8 Correct 42 ms 3916 KB Output is correct
9 Correct 40 ms 3968 KB Output is correct
10 Correct 51 ms 7792 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1196 KB Output is correct
2 Correct 10 ms 1228 KB Output is correct
3 Correct 31 ms 2864 KB Output is correct
4 Correct 26 ms 2508 KB Output is correct
5 Correct 55 ms 5412 KB Output is correct
6 Correct 47 ms 4332 KB Output is correct
7 Correct 54 ms 5372 KB Output is correct
8 Correct 47 ms 4536 KB Output is correct
9 Correct 46 ms 3996 KB Output is correct
10 Correct 46 ms 4348 KB Output is correct