oj.uz

답안 #500845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500845 2022-01-01T12:19:18 Z Stickfish Fireworks (APIO16_fireworks) C++17
7 / 100
 6 ms 7244 KB 
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

struct dpvl {
    ll l;
    ll r;
    ll mn; 

    dpvl() {}

    dpvl(ll l_, ll r_, ll mn_): l(l_), r(r_), mn(mn_) {}

    ll operator()(ll x) {
        if (l <= x && x <= r)
            return mn;
        return min(abs(l - x), abs(r - x)) + mn;
    }
};

const int MAXN = 300003;
const ll INF = 1.77013e18;
vector<pair<int, ll>> edg[MAXN];
pair<int, ll> root[MAXN];

ll get_vl(vector<dpvl>& v, ll x) {
    ll ans = 0;
    for (auto d : v) {
        ans += d(x);
        if (ans > INF)
            return INF;
    }
    return ans;
}

ll lower_bound_dir(vector<dpvl>& v, ll x) {
    ll lb = -2, ub = INF;
    while (ub - lb > 1) {
        ll mb = (lb + ub) / 2;
        ll t = get_vl(v, mb + 1);
        if (t == INF) {
            ub = mb;
            continue;
        }
        if (get_vl(v, mb + 1) - get_vl(v, mb) < x)
            lb = mb;
        else
            ub = mb;
    }
    return ub;
}


dpvl dfs(int v, int n) {
    if (v >= n) {
        return {root[v].second, root[v].second, 0};
    }
    vector<dpvl> ch;
    for (auto [u, d] : edg[v]) {
        ch.push_back(dfs(u, n));
    }
    ll l = lower_bound_dir(ch, 0);
    ll r = lower_bound_dir(ch, 1);
    ll t = get_vl(ch, l);
    //assert(t == get_vl(ch, r) && t < get_vl(ch, l - 1) && t < get_vl(ch, r + 1));
    //assert(r >= l && l >= 0);
    ll mn = 0;
    for (auto d : ch)
        mn += d(l);
    return {l + root[v].second, r + root[v].second, mn};
}

signed main() {
    int n, m;
    cin >> n >> m;
    ll addans = 0;
    for (int i = 1; i < n + m; ++i) {
        ll u, d;
        cin >> u >> d;
        --u;
        if (u >= n) {
            addans += d;
        } else {
            edg[u].push_back({i, d});
            root[i] = {u, d};
        }
    }
    cout << dfs(0, n).mn + addans << endl;
}

Compilation message

fireworks.cpp: In function 'dpvl dfs(int, int)':
fireworks.cpp:66:8: warning: unused variable 't' [-Wunused-variable]
   66 |     ll t = get_vl(ch, l);
      |        ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 4 ms 7220 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Incorrect 6 ms 7244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 4 ms 7220 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Incorrect 6 ms 7244 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 4 ms 7220 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Incorrect 6 ms 7244 KB Output isn't correct
14 Halted 0 ms 0 KB -