Submission #469064

#	Time	Username	Problem	Language	Result	Execution time	Memory
469064		ntabc05101	Ideal city (IOI12_city)	C++14	0 / 100	9 ms	1980 KiB

city

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

int DistanceSum(int N, int *X, int *Y) {
	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;
	}
		
	long long res = 0;
	for (int e = 0; e < 2; e++) {
		vector<int> pts[mxX];
		for (int i = 0; i < N; i++) {
			pts[X[i]].push_back(Y[i]);
		}
		int cur = 0, cnt = 0;
		vector<int> c, d, w;
		vector< vector<int> > adj(1);
		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);
				//cout << cur << " ";
				//cout << pts[i][j] << " ";
				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]) {
						//cout << " " << cur << " " << c[k] << "\n";
						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>());
				}
			}
			//cout << "\n";
			swap(c, d);
		}
		
		for (auto& ad: adj) {
			/*for (auto& _: ad) {
				cout << _ << " ";
			}
			cout << "\n";*/
			ad.resize(unique(ad.begin(), ad.end()) - ad.begin());
		}
		
		function<long long(int, int)> dfs = [&](int u, int p) {
			long long W = w[u];
			for (auto &to: adj[u]) {
				if (to != p) {
					int v = dfs(to, u);
					res += 1ll * v * (N - v);
					W += v;
				}
			}
			return W;
		};
		
		dfs(0, -1);
		
		for (int i = 0; i < N; i++) {
			swap(X[i], Y[i]);
		}
	}
	
	return res;
}

/*int main() {
	//cin.tie(0)->sync_with_stdio(0);
	
	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 (stderr)

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

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