Submission #197713

#	Time	Username	Problem	Language	Result	Execution time	Memory
197713		dolphingarlic	ČVENK (COI15_cvenk)	C++14	17 / 100	2538 ms	91332 KiB

cvenk

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll tot_dist = 0, ans = LLONG_MAX;

struct Node {
	ll x, y, l;
	Node *c[2];

	Node(ll X = 0, ll Y = 0): x(X), y(Y), l(0) {
		c[0] = c[1] = NULL;
	}

	Node* insert(Node *ins, int child) {
		l++;
		if (c[child] == NULL) {
			tot_dist += ins->x - x + ins->y - y;
			c[child] = ins;
			return ins;
		}
		if (ins->x < c[child]->x || ins->y < c[child]->y) {
			tot_dist += ins->x - x + ins->y - y;
			ins->c[child] = c[child];
			ins->l += c[child]->l;
			c[child] = ins;
			return ins;
		}
		if (ins->x > c[child]->x || ins->y > c[child]->y) {
			tot_dist += ins->x - c[child]->x + ins->y - c[child]->y;
			return c[child]->insert(ins, child);
		}
		tot_dist += ins->x - x + ins->y - y;
		return c[child];
	}
};

int n;
Node *root = new Node();

void dfs(Node *curr) {
	ans = min(ans, tot_dist);
	for (int i = 0; i < 2; i++) {
		if (curr->c[i] != NULL) {
			ll dx = curr->x - curr->c[i]->x + curr->y - curr->c[i]->y;
			tot_dist += dx * (2 * curr->c[i]->l - n);
			dfs(curr->c[i]);
			tot_dist -= dx * (2 * curr->c[i]->l - n);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		Node *curr = root;
		ll x, y, cx = 0, cy = 0;
		cin >> x >> y;
		for (int j = 30; ~j; j--) {
			if (x & (1 << j)) {
				cx |= (1 << j);
				curr = curr->insert(new Node(cx, cy), 0);
			}
			if (y & (1 << j)) {
				cy |= (1 << j);
				curr = curr->insert(new Node(cx, cy), 1);
			}
		}
		curr->l++;
	}
	dfs(root);
	cout << ans;
}

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