Submission #846483

#	Time	Username	Problem	Language	Result	Execution time	Memory
846483		vjudge1	ČVENK (COI15_cvenk)	C++17	100 / 100	2942 ms	223348 KiB

cvenk

#include <bits/stdc++.h>
#define mp(x...) array<int, 2>({x})
using namespace std;

constexpr static int MXN = 1e5 + 5;
constexpr static int MXLOG = 31;
constexpr static int MXM = MXN * MXLOG;

vector<array<int, 2>> g[MXN];

int counts[MXM];
int redge[MXM], ledge[MXM], rright[MXM], lleft[MXM], x[MXM], y[MXM], p[MXM], subsize[MXM];
int root;

map<array<int, 2>, int> pos;
set<array<int, 2>> intervals;


int nxt = 0;
int construct(int _x, int _y, int step)
{
	if (step == -1)
	{
		counts[nxt] = pos[mp(_x, _y)];
		x[nxt] = _x;
		y[nxt] = _y;
		redge[nxt] = nxt;
		ledge[nxt] = nxt;
		return nxt++;
	}
	int mv = 1<<step;
	int l = -1, r = -1;
	if (intervals.find(mp(_x+mv, _y)) != intervals.end())
		l = construct(_x+mv, _y, step-1);
	if (intervals.find(mp(_x, _y+mv)) != intervals.end())
		r = construct(_x, _y+mv, step-1);
	int current = construct(_x, _y, step-1);
	if (l != -1)
	{
		lleft[ledge[current]] = l;
		p[l] = ledge[current];
		ledge[current] = ledge[l];
	}
	if (r != -1)
	{
		rright[redge[current]] = r;
		p[r] = redge[current];
		redge[current] = redge[r];
	}
	return current;
}


void dfs1(int node)
{
	subsize[node] = counts[node];
	if (lleft[node] != -1)
	{
		dfs1(lleft[node]);
		subsize[node] += subsize[lleft[node]];
	}
	if (rright[node] != -1)
	{
		dfs1(rright[node]);
		subsize[node] += subsize[rright[node]];
	}
}

int dfs2(int node)
{
	if (lleft[node] != -1 && subsize[lleft[node]] * 2 > subsize[root])
		return dfs2(lleft[node]);
	if (rright[node] != -1 && subsize[rright[node]] * 2 > subsize[root])
		return dfs2(rright[node]);
	return node;
}

void dfs3(int node, int parent, int dist);

void dod(int node, int parent, int dist, int o)
{
	if (o != -1 && o != parent)
	{
		int ndist = dist + abs(x[node] - x[o]) + abs(y[node] - y[o]);
		dfs3(o, node, ndist);
	}
}
	
int64_t sum;
void dfs3(int node, int parent, int dist)
{
	sum += counts[node] * dist;
	dod(node, parent, dist, lleft[node]);
	dod(node, parent, dist, rright[node]);
	dod(node, parent, dist, p[node]);
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		if (pos.find(mp(x, y)) == pos.end())
			pos[mp(x, y)] = 0;
		pos[mp(x, y)]++;
		while(x || y)
		{
			intervals.insert({x, y});
			int mx = x & (-x), my = y & (-y);
			if (mx == 0 || (my != 0 && mx > my)) 
				y -= my;
			else 
				x -= mx;
		}
	}
	for (int i = 0; i < MXM; i++)
		lleft[i] = -1, rright[i] = -1, p[i] = -1;
	root = construct(0, 0, MXLOG-1);
	dfs1(root);
	int center = dfs2(root);
	dfs3(center, -1, 0);
	cout << sum << "\n";

}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40