Submission #197717

#TimeUsernameProblemLanguageResultExecution timeMemory
197717dolphingarlicČVENK (COI15_cvenk)C++14
60 / 100
3053 ms93148 KiB
#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) { c[child] = ins; return ins; } if (ins->x < c[child]->x || ins->y < c[child]->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) return c[child]->insert(ins, child); return c[child]; } }; int n; Node *root = new Node(); void dfs(Node *curr) { // cout << curr->x << ' ' << curr->y << ' ' << curr->l << ' ' << tot_dist << '\n'; 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; tot_dist += 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...