Submission #469067

#	Time	Username	Problem	Language	Result	Execution time	Memory
469067		ntabc05101	Ideal city (IOI12_city)	C++14	32 / 100	10 ms	1100 KiB

city

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

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);
			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) {
			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);
	
	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:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for (int j = 0; j < pts[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
city.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      while (k < pts[i - 1].size() && pts[i - 1][k] < pts[i][j]) {
      |             ~~^~~~~~~~~~~~~~~~~~~
city.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |      if (k < pts[i - 1].size() && pts[i - 1][k] == pts[i][j]) {
      |          ~~^~~~~~~~~~~~~~~~~~~
city.cpp:62:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (j == pts[i].size() - 1 || pts[i][j] + 1 < pts[i][j + 1]) {
      |         ~~^~~~~~~~~~~~~~~~~~~~

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