oj.uz

Submission #650808

# Submission time Handle Problem Language Result Execution time Memory
650808 2022-10-15T12:05:02 Z jasen_penchev ČVENK (COI15_cvenk) C++14
100 / 100
 605 ms 2952 KB 
#include <iostream>
#include <utility>
#include <random>
#define endl '\n'
#define fi first
#define se second
using namespace std;

mt19937 rg(4209008);

const int MAXN = 100000;
const int LOG = 34;

int n;
pair<int, int> p[MAXN + 5];

pair<int, int> kth_ancestor(int x, int y, long long k)
{
    if (k == 0) return make_pair(x, y);
    if (x == 0) return make_pair(x, y - k);
    if (y == 0) return make_pair(x - k, y);

    int bx = (x & (-x)), by = (y & (-y));
    if (bx < by) return kth_ancestor(x - min(1ll * bx, k), y, k - min(1ll * bx, k));
    else return kth_ancestor(x, y - min(1ll * by, k), k - min(1ll * by, k));
}

long long depth(pair<int, int> x)
{
    return (1ll * x.fi + 1ll * x.se);
}

pair<int, int> lca(pair<int, int> u, pair<int, int> v)
{
    long long du = depth(u), dv = depth(v);
    if (du > dv)
    {
        swap(u, v);
        swap(du, dv);
    }

    for (int i = LOG; i >= 0; -- i)
    {
        if (dv - (1ll << i) >= du)
        {
            v = kth_ancestor(v.fi, v.se, (1ll << i));
            dv -= (1ll << i);
        }
    }

    for (int i = LOG; i >= 0; -- i)
    {
        if ((1ll << i) > du) continue;
        if (kth_ancestor(u.fi, u.se, (1ll << i)) != kth_ancestor(v.fi, v.se, (1ll << i)))
        {
            u = kth_ancestor(u.fi, u.se, (1ll << i));
            v = kth_ancestor(v.fi, v.se, (1ll << i));
            du -= (1ll << i);
            dv -= (1ll << i);
        }
    }

    if (u == v) return u;
    return kth_ancestor(u.fi, u.se, 1);
}

long long dist(pair<int, int> u, pair<int, int> v)
{
    return (depth(u) + depth(v) - 2 * depth(lca(u, v)));
}

int cnt_descendants(pair<int, int> u)
{
    int cnt = 0;
    long long du = depth(u);
    for (int i = 1; i <= n; ++ i)
    {
        long long di = depth(p[i]);
        if (du <= di and kth_ancestor(p[i].fi, p[i].se, di - du) == u) cnt++;
    }
    return cnt;
}

long long solve(pair<int, int> u)
{
    if (cnt_descendants(u) < (n + 1) / 2)
    {
        long long du = depth(u);
        for (int i = LOG; i >= 0; -- i)
        {
            if ((1ll << i) > du) continue;
            auto v = kth_ancestor(u.fi, u.se, (1ll << i));
            if (cnt_descendants(v) < (n + 1) / 2)
            {
                u = v;
                du -= (1ll << i);
            }
        }
        u = kth_ancestor(u.fi, u.se, 1);
    }

    if ((((u.fi + 1) & u.se) == 0) and cnt_descendants(make_pair(u.fi + 1, u.se)) >= (n + 1) / 2) return -1;
    if (((u.fi & (u.se + 1)) == 0) and cnt_descendants(make_pair(u.fi, u.se + 1)) >= (n + 1) / 2) return -1;

    long long ret = 0;
    for (int i = 1; i <= n; ++ i)
    {
        ret += dist(u, p[i]);
    }
    return ret;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; ++ i)
    {
        cin >> p[i].fi >> p[i].se;
    }

    while (true)
    {
        int i0 = (rg() % n) + 1;
        long long ans = solve(p[i0]);
        if (ans != -1)
        {
            cout << ans << endl;
            return 0;
        }
    }

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1724 KB Output is correct
2 Correct 80 ms 1724 KB Output is correct
3 Correct 33 ms 1632 KB Output is correct
4 Correct 28 ms 1524 KB Output is correct
5 Correct 43 ms 1628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 2952 KB Output is correct
2 Correct 411 ms 2948 KB Output is correct
3 Correct 130 ms 2440 KB Output is correct
4 Correct 88 ms 2432 KB Output is correct
5 Correct 98 ms 2368 KB Output is correct