Submission #556461

#	Time	Username	Problem	Language	Result	Execution time	Memory
556461		InternetPerson10	Fireworks (APIO16_fireworks)	C++17	7 / 100	1 ms	340 KiB

fireworks

#include <bits/stdc++.h>
typedef __int128 ll;

using namespace std;

struct Vertex {
    // [l, r] is the median range
    // s is the number in the current fuse
    ll l = -1, r = -1, s, cost = 0;
    vector<Vertex*> children;
    Vertex(ll a) {
        s = a;
    }
    ~Vertex() {
        for(Vertex* v : children) {
            delete v;
        }
        children.clear();
    }
    void addChild(Vertex* v) {
        children.push_back(v);
    }
    void calcMedian() {
        if(children.size() == 0) {
            l = r = s;
            return;
        }
        vector<pair<ll, ll>> ranges;
        for(Vertex* v : children) {
            v->calcMedian();
            cost += v->cost;
            ranges.push_back({v->l, v->r});
        }
        auto rangDist = [&](ll le, ll ri, ll x) {
            if(le <= x && x <= ri) return (ll)0;
            if(ri < x) return (ll)(x - ri);
            if(x < le) return (ll)(le - x);
            assert(false);
            return (ll)0;
        };
        auto calcTot = [&](ll x) {
            ll tot = 0;
            for(auto [le, ri] : ranges) {
                tot += rangDist(le, ri, x);
            }
            return tot;
        };
        // Step 1: Finding the answer
        ll le = -1, ri = 1e18 + 1;
        while(le < ri - 4) {
            ll x1 = (le + le + ri) / 3;
            ll x2 = (le + ri + ri) / 3;
            ll tot1 = calcTot(x1);
            ll tot2 = calcTot(x2);
            if(tot1 == tot2) {
                le = x1;
                ri = x2;
            }
            if(tot1 > tot2) le = x1;
            if(tot1 < tot2) ri = x2;
        }
        ll ans = (ll)1e18 + 1;
        for(ll x = le; x <= ri; x++) {
            ans = min(ans, calcTot(x));
        }
        ll best = le;
        while(calcTot(best) != ans) best++;
        cost += ans;
        // Step 2: Finding the range that gives that answer
        le = 0, ri = best;
        while(le != ri - 1) {
            ll mid = (le + ri) / 2;
            if(calcTot(mid) != ans) le = mid;
            else ri = mid;
        }
        l = ri + s;
        le = best, ri = (ll)1e18 + 1;
        while(le != ri - 1) {
            ll mid = (le + ri) / 2;
            if(calcTot(mid) == ans) le = mid;
            else ri = mid;
        }
        r = le + s;
    }
};

vector<Vertex*> tree;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    tree.push_back(new Vertex(0));
    for(int i = 1; i < n + m; i++) {
        long long p, c;
        cin >> p >> c;
        tree.push_back(new Vertex(c));
        tree[p-1]->addChild(tree[i]);
    }
    tree[0]->calcMedian();
    ll x = tree[0]->cost;
    cout << (long long)tree[0]->cost << '\n';
    tree.clear();
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:102:8: warning: unused variable 'x' [-Wunused-variable]
  102 |     ll x = tree[0]->cost;
      |        ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45