Submission #846483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
846483	2023-09-07T15:49:38 Z	vjudge1	ČVENK (COI15_cvenk)	C++17	100 / 100	2942 ms	223348 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	50008 KB	Output is correct
2	Correct	6 ms	50268 KB	Output is correct
3	Correct	6 ms	50012 KB	Output is correct
4	Correct	6 ms	50268 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	50268 KB	Output is correct
2	Correct	8 ms	50260 KB	Output is correct
3	Correct	8 ms	50268 KB	Output is correct
4	Correct	8 ms	50260 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	50864 KB	Output is correct
2	Correct	109 ms	50860 KB	Output is correct
3	Correct	47 ms	50008 KB	Output is correct
4	Correct	47 ms	50188 KB	Output is correct
5	Correct	66 ms	50364 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2917 ms	223348 KB	Output is correct
2	Correct	2942 ms	223096 KB	Output is correct
3	Correct	1058 ms	156916 KB	Output is correct
4	Correct	1135 ms	164824 KB	Output is correct
5	Correct	1346 ms	168524 KB	Output is correct