Submission #103816

#	Time	Username	Problem	Language	Result	Execution time	Memory
103816		Anai	Ideal city (IOI12_city)	C++14	100 / 100	187 ms	15352 KiB

city

#ifdef HOME
	#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

using i64 = long long;

struct Position {
	int ycoord, sheet; };

vector<Position> layers[N];
set<int> g[N];
int siz[N], weight[N];


int n, h, sheets;
i64 ant;

static Position at(int x, int y) {
	if (layers[x].empty())
		return Position {-1, -1};

	int pos = 0;
	for (int msk = 1 << 16; msk > 0; msk/= 2)
		if (pos + msk < layers[x].size() && layers[x][pos + msk].ycoord <= y)
			pos+= msk;
	if (layers[x][pos].ycoord == y)
		return layers[x][pos];
	else
		return Position {-1, -1}; }

static void normalize(int x[], int y[]) {
	map<int, int> mpx, mpy;
	int ptr;

	for (int i = 0; i < n; ++i) {
		mpx[x[i]] = 0;
		mpy[y[i]] = 0; }

	ptr = 0;
	for (auto &i: mpx)
		i.second = ++ptr;
	ptr = 0;
	for (auto &i: mpy)
		i.second = ++ptr;

	h = mpx.size();
	for (int i = 0; i < n; ++i) {
		x[i] = mpx[x[i]];
		y[i] = mpy[y[i]]; } }

static void sheet_decomposition() {
	sheets = 0;
	for (int layer = 1; layer <= h; ++layer) {
		sort(begin(layers[layer]), end(layers[layer]), [&](const Position &a, const Position &b) {
			return a.ycoord < b.ycoord; });

		for (int lst = -1, i = 0; i < layers[layer].size(); ++i) {
			if (layers[layer][i].ycoord != lst + 1) {
				sheets+= 1;
				siz[sheets] = 0; }

			siz[sheets]+= 1;
			layers[layer][i].sheet = sheets;
			lst = layers[layer][i].ycoord; } } }

static void build_graph() {
	for (int x = 1; x <= h; ++x) {
		for (auto component: layers[x]) {
			int y = component.ycoord;

			for (int dir = 0; dir < 4; ++dir) {
				int nx(x + dx[dir]), ny(y + dy[dir]);
				Position link = at(nx, ny);
				if (link.sheet != component.sheet && link.sheet != -1)
					g[component.sheet].insert(link.sheet); } } } }

static void solve(int u, int far = -1) {
	weight[u] = siz[u];
	for (auto v: g[u]) if (v != far) {
		solve(v, u);
		weight[u]+= weight[v]; } }


int DistanceSum(int _n, int x[], int y[]) {
	n = _n;
	normalize(x, y);
	for (int i = 0; i < n; ++i)
		layers[x[i]].push_back({y[i], -1});

	sheet_decomposition();
	build_graph();
	
	solve(1);
	for (int i = 1; i <= sheets; ++i)
		ant = (ant + i64(weight[i]) * (n - weight[i])) % int(1e9);

	for (int i = 1; i <= h; ++i)
		layers[i].clear();

	for (int i = 0; i < n; ++i) {
		swap(x[i], y[i]);
		g[i + 1].clear(); }

	for (int i = 0; i < n; ++i) {
		layers[x[i]].push_back({y[i], -1});
		h = max(h, x[i]); }

	sheet_decomposition();
	build_graph();
	
	solve(1);
	for (int i = 1; i <= sheets; ++i)
		ant = (ant + i64(weight[i]) * (n - weight[i])) % int(1e9);

	return int(ant); }

Compilation message (stderr)

city.cpp: In function 'Position at(int, int)':
city.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pos + msk < layers[x].size() && layers[x][pos + msk].ycoord <= y)
       ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
city.cpp: In function 'void sheet_decomposition()':
city.cpp:63:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int lst = -1, i = 0; i < layers[layer].size(); ++i) {
                             ~~^~~~~~~~~~~~~~~~~~~~~~

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