oj.uz

Submission #556462

# Submission time Handle Problem Language Result Execution time Memory
556462 2022-05-03T08:03:13 Z InternetPerson10 Fireworks (APIO16_fireworks) C++17
7 / 100
 1 ms 212 KB 
#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;
        ll minVal = 1e18;
        for(Vertex* v : children) {
            v->calcMedian();
            cost += v->cost;
            ranges.push_back({v->l, v->r});
            minVal = min(minVal, v->l - v->s);
        }
        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 = minVal, 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 = minVal, 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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -