Submission #304689

#	Time	Username	Problem	Language	Result	Execution time	Memory
304689		AM1648	ČVENK (COI15_cvenk)	C++17	100 / 100	931 ms	26744 KiB

cvenk

/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 200010;
const ll maxalg = 30;

ll n, m, par[maxn], sz[maxn];
pii ver[maxn], tour[maxn];
vi subt[maxn];
map<pii, ll> cnt;

inline ll ht(pii &x) {
    return x.F + x.S;
}

pii kth_par(pii x, ll k) {
    while (x.F && x.S) {
        ll lb1 = x.F & -x.F;
        ll lb2 = x.S & -x.S;
        if (lb1 < lb2) {
            if (lb1 >= k) return {x.F - k, x.S};
            else x.F -= lb1, k -= lb1;
        } else {
            if (lb2 >= k) return {x.F, x.S - k};
            else x.S -= lb2, k -= lb2;
        }
    }
    if      (x.F >= k) return {x.F - k, x.S};
    else if (x.S >= k) return {x.F, x.S - k};
    else return {0, 0};
}

bool st_cmp(pii &a, pii &b) {
    if (ht(a) < ht(b)) {
        pii bb = kth_par(b, ht(b) - ht(a));
        return a == bb ? true : a.F < bb.F;
    } else {
        pii aa = kth_par(a, ht(a) - ht(b));
        return aa == b ? false : aa.F < b.F;
    }
}

bool a_subt_b(pii &a, pii &b) {
    return (ht(a) >= ht(b)) && (kth_par(a, ht(a) - ht(b)) == b);
}

pii lca(pii a, pii b) {
    if (ht(a) < ht(b)) swap(a, b);
    a = kth_par(a, ht(a) - ht(b));
    if (a == b) return a;
    forir (i, maxalg) {
        pii aa = kth_par(a, 1 << i), bb = kth_par(b, 1 << i);
        if (aa != bb) a = aa, b = bb;
    }
    return kth_par(a, 1);
}

void make_virt_tree() {
    sort(ver, ver + n, st_cmp);
    m = unique(ver, ver + n) - ver;
    fori (i, m - 1) {
        ver[m + i] = lca(ver[i], ver[i + 1]);
    }
    m += m - 1;
    sort(ver, ver + m, st_cmp);
    m = unique(ver, ver + m) - ver;
    forifrom (i, 1, m) {
        par[i] = i - 1;
        while (par[i] && !a_subt_b(ver[i], ver[par[i]])) par[i] = par[par[i]];
        subt[par[i]].eb(i);
    }
}

void dfs_sz(ll x) {
    sz[x] = cnt[ver[x]];
    for (auto y : subt[x]) {
        dfs_sz(y);
        sz[x] += sz[y];
    }
}

ll dfs_cent(ll x) {
    for (auto y : subt[x]) if (sz[y] * 2 > n) return dfs_cent(y);
    return x;
}

long long sum_dist(ll x) {
    long long s = 0;
    fori (i, n) {
        pii c = lca(tour[i], ver[x]);
        s += ht(tour[i]) + ht(ver[x]) - ht(c) * 2;
    }
    return s;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;
    fori (i, n) {
        ll r, c; cin >> r >> c;
        ver[i] = tour[i] = {r, c};
        ++cnt[{r, c}];
    }

    make_virt_tree();

    dfs_sz(0);
    ll cent = dfs_cent(0);

    long long ans = sum_dist(cent);
    cout << ans << '\n';

}

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