Submission #410549

#	Time	Username	Problem	Language	Result	Execution time	Memory
410549		PurpleCrayon	ČVENK (COI15_cvenk)	C++17	38 / 100	3090 ms	521092 KiB

cvenk

#include "bits/stdc++.h"
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 2e5+10, MOD = 1e9+7, MAXL = 34;
const int INF = 1e9+10;

map<ar<ll, 2>, int> idx;
vector<ar<ll, 2>> anc[MAXN*2];

int lsb(ll x){ return 1+__builtin_ctzll(x); }
ll dep(ar<ll, 2> c){ return c[0]+c[1]; }
ar<ll, 2> par(ar<ll, 2> c) {
    if (!c[0] || !c[1]) {
        return {max(0ll, c[0]-1), max(0ll, c[1]-1)};
    }
    if (lsb(c[0]) < lsb(c[1])) return {c[0]-1, c[1]};
    else return {c[0], c[1]-1};
}
ar<ll, 2> jmp(ar<ll, 2> c, ll d) {
    if (!d) return c;

    ll v = d;
    ll lb = c[0]&(-c[0]), rb = c[1]&(-c[1]);

    if (c[0]) v = min(v, lb);
    if (c[1]) v = min(v, rb);

    if (!c[1]) return jmp({c[0]-v, c[1]}, d-v);
    if (!c[0]) return jmp({c[0], c[1]-v}, d-v);
    if (lb < rb) return jmp({c[0]-v, c[1]}, d-v); 
    else return jmp({c[0], c[1]-v}, d-v);
}
ar<ll, 2> binjmp(ar<ll, 2> c, int d) {
    if (idx.count(c)) return anc[idx[c]][d];
    int i = sz(idx); idx[c] = i;
    anc[i].resize(MAXL);
    for (int j = 0; j < MAXL; j++) anc[i][j] = jmp(c, 1ll<<j);
    return anc[i][d];
}
ar<ll, 2> fast_lca(ar<ll, 2> a, ar<ll, 2> b) {
    if (dep(a) < dep(b)) swap(a, b);
    a = jmp(a, dep(a)-dep(b));
    if (a == b) return a;
    //cerr << a[0] << ' ' << a[1] << endl;

    for (ll k = 40; k >= 0; k--) {
        ll cur = 1ll<<k;
        if (dep(a) >= cur && dep(b) >= cur) {
            ar<ll, 2> na = binjmp(a, k), nb = binjmp(b, k);
            if (na != nb) {
                a = na, b = nb;
            }
        }
    }
    return par(a);
}
ar<ll, 2> lca(ar<ll, 2> a, ar<ll, 2> b) {
    if (dep(a) < dep(b)) swap(a, b);
    a = jmp(a, dep(a)-dep(b));
    if (a == b) return a;
    //cerr << a[0] << ' ' << a[1] << endl;

    for (ll k = MAXL-1; k >= 0; k--) {
        ll cur = 1ll<<k;
        if (dep(a) >= cur && dep(b) >= cur) {
            ar<ll, 2> na = jmp(a, cur), nb = jmp(b, cur);
            if (na != nb) {
                a = na, b = nb;
            }
        }
    }
    return par(a);
}
ar<ll, 2> lca_slow(ar<ll, 2> a, ar<ll, 2> b) {
    while (a != b) {
        if (dep(a) < dep(b)) swap(a, b);
        a = par(a);
    }
    return a;
}
ll dist(ar<ll, 2> a, ar<ll, 2> b) {
    return dep(a)+dep(b)-2*dep(lca(a, b));
}
bool comp(ar<ll, 2> a, ar<ll, 2> b) {
    if (a == b) return 0;
    ar<ll, 2> l = fast_lca(a, b);
    if (a == l) return 1;
    if (b == l) return 0;

    ll k1 = dep(a)-dep(l)-1, k2 = dep(b)-dep(l)-1;
    ar<ll, 2> a1 = jmp(a, k1), a2 = jmp(b, k2);
    return a1 < a2;
}
int n;

ar<ll, 2> gen() {
    ll a = ll(rand())|(ll(rand())<<15);
    ll b = 0;
    for (int i = 0; i < 30; i++) {
        if ((a>>i)&1^1) {
            b |= (rand()&1)<<i;
        }
    }
    assert((a&b) == 0);
    //cerr << a << ' ' << b << endl;
    return {a, b};
}

vector<int> sub;
vector<vector<int>> adj;

int dfs(int c=0, int p=-1) {
    for (auto nxt : adj[c]) if (nxt != p) sub[c] += dfs(nxt, c);
    return sub[c];
}
int dfsAns(int c=0, int p=-1) {
    for (auto nxt : adj[c]) if (nxt != p) {
        int val = sub[nxt] - (sub[0] - sub[nxt]);
        if (val > 0) return dfsAns(nxt, c);
    }
    return c;
}
int solve_tree(vector<ar<int, 2>> ed, vector<int> cost) {
    sub = cost; adj.resize(sz(cost));
    for (auto e : ed) adj[e[0]].push_back(e[1]), adj[e[1]].push_back(e[0]);
    dfs();
    return dfsAns();
}
void solve(){
    cin >> n;
    srand(time(0));
    vector<ar<ll, 2>> a(n), b;
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        //a[i] = gen();
    }
    b = a;
    sort(a.begin(), a.end(), comp);

    set<ar<ll, 2>> s;
    for (int i = 0; i < n-1; i++) {
        a.push_back(fast_lca(a[i], a[i+1]));
    }

    sort(a.begin(), a.end(), comp);
    a.erase(unique(a.begin(), a.end()), a.end());

    map<ar<ll, 2>, int> mp;
    for (int i = 0; i < sz(a); i++) mp[a[i]] = i;

    vector<int> cost(sz(a));
    for (int i = 0; i < n; i++) cost[mp[b[i]]]++;

    vector<ar<int, 2>> ed;
    for (int i = 0; i < sz(a)-1; i++) {
        auto v1 = a[i], v2 = a[i+1];
        ed.push_back({mp[fast_lca(v1, v2)], mp[v2]});
    }

    int ROOT = solve_tree(ed, cost);

    auto c = a[ROOT];
    ll ans = 0;
    for (int i = 0; i < n; i++) ans += dist(c, b[i]);
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    //cin >> T;
    while (T--) solve();
}

Compilation message (stderr)

cvenk.cpp: In function 'std::array<long long int, 2> gen()':
cvenk.cpp:103:19: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  103 |         if ((a>>i)&1^1) {
      |             ~~~~~~^~

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