oj.uz

Submission #197717

# Submission time Handle Problem Language Result Execution time Memory
197717 2020-01-22T13:34:02 Z dolphingarlic ČVENK (COI15_cvenk) C++14
60 / 100
 3000 ms 93148 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) {
            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;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 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
21.0 / 21.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 25404 KB Output is correct
2 Correct 206 ms 26104 KB Output is correct
3 Correct 69 ms 17016 KB Output is correct
4 Correct 66 ms 15736 KB Output is correct
5 Correct 74 ms 17272 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2514 ms 91376 KB Output is correct
2 Correct 2522 ms 93148 KB Output is correct
3 Execution timed out 3053 ms 7900 KB Time limit exceeded
4 Halted 0 ms 0 KB -