Submission #61720

#	Time	Username	Problem	Language	Result	Execution time	Memory
61720		aome	Ideal city (IOI12_city)	C++17	23 / 100	908 ms	61564 KiB

city

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int mod = 1e9;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, res;
int par[N];
int sz[N];
int T, low[N], num[N];
vector<int> G[N], vec[N];
vector< pair<int, int> > G2[N];
map< pair<int, int>, int > label;
map< pair<int, int>, bool > bridge;

int find(int u) {
	return u == par[u] ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	par[find(u)] = find(v);
}

void dfs(int u, int p) {
	low[u] = num[u] = ++T;
	for (auto v : G[u]) {
		if (v == p) continue;
		if (num[v]) low[u] = min(low[u], num[v]);
		else {
			dfs(v, u), low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				bridge[{u, v}] = bridge[{v, u}] = 1;
			}
		}
	}
}

void dfs2(int u, int p) {
	sz[u] = vec[u].size();
	for (auto v : G2[u]) {
		if (p == v.first) continue;
		dfs2(v.first, u), sz[u] += sz[v.first];
	}
}

void solve(vector< pair<int, int> > vec[2]) {
	for (int i = 0; i < 2; ++i) {
		sort(vec[i].begin(), vec[i].end());
		int sum;
		sum = 0;
		for (auto j : vec[i]) {
			res = (res + 1LL * sum * j.second % mod * j.first) % mod;
			sum = (sum + j.second) % mod;
		}
		sum = 0;
		reverse(vec[i].begin(), vec[i].end());
		for (auto j : vec[i]) {
			res = (res + mod - 1LL * sum * j.second % mod * j.first % mod) % mod;
			sum = (sum + j.second) % mod;
		}
	}
}

int DistanceSum(int n, int *X, int *Y) {
	for (int i = 0; i < n; ++i) {
		label[{X[i], Y[i]}] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			int x = X[i] + dx[j], y = Y[i] + dy[j];
			if (label.count({x, y})) {
				int id = label[{x, y}];
				G[i].push_back(id);
			}
		}
	}
	dfs(0, 0);
	for (int i = 0; i < n; ++i) par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (bridge[{i, j}]) continue;
			join(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (bridge[{i, j}]) {
				G2[find(i)].push_back({find(j), i});
			}
		}
	}
	for (int i = 0; i < n; ++i) vec[find(i)].push_back(i);
	for (int i = 0; i < n; ++i) {
		if (find(i) == i) {
			dfs2(i, i); break;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (find(i) != i) continue;
		for (auto j : G2[i]) {
			if (sz[i] > sz[j.first]) {
				res = (res + 1LL * sz[j.first] * (n - sz[j.first])) % mod;
			}
		}
		vector< pair<int, int> > vec2[2];
		for (auto j : vec[i]) {
			vec2[0].push_back({X[j], 1});
			vec2[1].push_back({Y[j], 1});
		}
		for (auto j : G2[i]) {
			int tmp;
			if (sz[i] > sz[j.first]) tmp = sz[j.first];
			else tmp = n - sz[i];
			vec2[0].push_back({X[j.second], tmp});
			vec2[1].push_back({Y[j.second], tmp});
		}
		solve(vec2);
	}
	return res;
}

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