oj.uz

Submission #197713

# Submission time Handle Problem Language Result Execution time Memory
197713 2020-01-22T13:26:11 Z dolphingarlic ČVENK (COI15_cvenk) C++14
17 / 100
 2538 ms 91332 KB 
#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.0 / 17.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 25496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2538 ms 91332 KB Output isn't correct
2 Halted 0 ms 0 KB -