oj.uz

답안 #846483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846483 2023-09-07T15:49:38 Z vjudge1 ČVENK (COI15_cvenk) C++17
100 / 100
 2942 ms 223348 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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