oj.uz

Submission #103816

# Submission time Handle Problem Language Result Execution time Memory
103816 2019-04-02T19:25:00 Z Anai Ideal city (IOI12_city) C++14
100 / 100
 187 ms 15352 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 10 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7488 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 11 ms 7552 KB Output is correct
6 Correct 13 ms 7468 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 13 ms 7424 KB Output is correct
10 Correct 10 ms 7552 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8064 KB Output is correct
2 Correct 25 ms 8320 KB Output is correct
3 Correct 46 ms 8824 KB Output is correct
4 Correct 52 ms 9464 KB Output is correct
5 Correct 86 ms 10232 KB Output is correct
6 Correct 89 ms 11384 KB Output is correct
7 Correct 98 ms 11088 KB Output is correct
8 Correct 86 ms 10104 KB Output is correct
9 Correct 102 ms 11080 KB Output is correct
10 Correct 169 ms 15352 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9004 KB Output is correct
2 Correct 30 ms 8696 KB Output is correct
3 Correct 70 ms 11044 KB Output is correct
4 Correct 83 ms 10280 KB Output is correct
5 Correct 134 ms 14584 KB Output is correct
6 Correct 116 ms 11948 KB Output is correct
7 Correct 136 ms 14388 KB Output is correct
8 Correct 115 ms 12312 KB Output is correct
9 Correct 103 ms 11152 KB Output is correct
10 Correct 187 ms 11384 KB Output is correct