Submission #587386

#	Time	Username	Problem	Language	Result	Execution time	Memory
587386		GioChkhaidze	Ideal city (IOI12_city)	C++14	100 / 100	347 ms	20800 KiB

city

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 1e5 + 5;

ll tot[Nn], ans, mod = 1e9;
int n, id[Nn], x[Nn], y[Nn], c[Nn];
int a[4] = {1, -1, 0, 0};
int b[4] = {0, 0, 1, -1};
map < pair < int , int > , int > f;
vector < int > v[Nn];

void dfs(int x, int p) {
	tot[x] = c[x];
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
		tot[x] += tot[to];
	}
	ans += (tot[x] * (n - tot[x])) % mod;
	ans %= mod;
}

void solve() {
	vector < pair < pair < int , int > , int > > s;
	for (int i = 0; i < n; ++i) {
		f[{x[i], y[i]}] = i;
		s.pb({{x[i], y[i]}, i});
	}
	sort(s.begin(), s.end());
	int nd = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (!i || (s[i - 1].f.f != s[i].f.f || s[i - 1].f.s + 1 < s[i].f.s)) ++nd;
		id[s[i].s] = nd, ++c[nd];
	}
	vector < pair < int , int > > ss;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			int Ax = x[i] + a[j], Ay = y[i] + b[j]; 
			if (f.find({Ax, Ay}) != f.end()) {
				int A = id[i];
				int B = id[f[{Ax, Ay}]];
				if (A > B) swap(A, B);
				ss.pb({A, B});
			}
		}
	}
	sort(ss.begin(), ss.end());
	for (int i = 0; i < ss.size(); ++i) {
		if (!i || ss[i - 1] != ss[i]) {
			v[ss[i].f].pb(ss[i].s);
			v[ss[i].s].pb(ss[i].f);
		}
	}
	dfs(1, 1);
}

void clear() {
	f.clear();
	for (int i = 1; i <= n; ++i) {
		v[i].clear(), c[i] = tot[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		swap(x[i], y[i]);
	}
}

int DistanceSum(int nn, int *X, int *Y) {
	n = nn;
	for (int i = 0; i < n; ++i) {
		x[i] = X[i], y[i] = Y[i];
	}
	solve();
	clear();
	solve();
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
city.cpp: In function 'void solve()':
city.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
city.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < ss.size(); ++i) {
      |                  ~~^~~~~~~~~~~

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