oj.uz

Submission #410547

# Submission time Handle Problem Language Result Execution time Memory
410547 2021-05-23T00:30:39 Z PurpleCrayon ČVENK (COI15_cvenk) C++17
60 / 100
 3000 ms 5948 KB 
#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;
const int INF = 1e9+10;

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> 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 = 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 = 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(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[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

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

Subtask #1
17.0 / 17.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2036 ms 5896 KB Output is correct
2 Correct 2045 ms 5948 KB Output is correct
3 Correct 133 ms 5028 KB Output is correct
4 Correct 151 ms 4988 KB Output is correct
5 Correct 467 ms 5264 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 3424 KB Time limit exceeded
2 Halted 0 ms 0 KB -