Submission #1326515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326515		absolut3	Fireworks (APIO16_fireworks)	C++20	0 / 100	1 ms	332 KiB

fireworks

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define sz(x) (ll)(x.size())
#define pii pair < int, int >
#define pll pair < ll, ll >

#define debug(x) cerr << (#x) << " = " << (x) << endl

const int mod = 1e9 + 7;
const int N = 1e5+1;
const ll OO = 1e18;

template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }

template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }

int n, m;
vector < pii > g[N];
pll res[N];
ll add[N], w[N];

int calc (int i, int l, int r) {
    if (!r || l <= i && i <= r)
        return 0;
    return min(abs(i - l), abs(i - r));
}

void dfs (int v) {
    map < ll, int > mp;
    for (auto [u, wi] : g[v]) {
        w[u] = w[v] + wi;
        dfs(u);
        add[v] += add[u];
        if (res[u].first) {
            mp[w[v]]++;
            mp[res[u].first]--;
            mp[res[u].second]--;
        }
    }
    if (v >= n) {
        res[v] = {w[v], w[v]};
    } else {
        res[v] = {10000, 0};
        ll mn = OO;
        for (int i = w[v]; i <= 305; ++i) {
            ll ri = 0;
            for (auto [u, wi] : g[v])
                ri += calc(i, res[u].first, res[u].second);
            umn(mn, ri);
        }
        for (int i = w[v]; i <= 305; ++i) {
            ll ri = 0;
            for (auto [u, wi] : g[v])
                ri += calc(i, res[u].first, res[u].second);
            if (ri == mn) {
                umn(res[v].first, (ll)i);
                umx(res[v].second, (ll)i);
            }
        }
        add[v] += mn;
        if (mn == 0) res[v] = {0ll, 0ll};
    }
//    cout << v << " " << res[v].first << " " << res[v].second << "\n";
}

void slv () {
    cin >> n >> m;
    for (int i = 1, p, c; i < n + m; ++i) {
        cin >> p >> c;
        g[p - 1].pb({i, c});
    }
    dfs(0);
    cout << add[0];
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
//    cin >> test;
    while (test--) {
        slv();
        cout << "\n";
    }
}

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