Submission #899273

#	Time	Username	Problem	Language	Result	Execution time	Memory
899273		Denisov	Fireworks (APIO16_fireworks)	C++14	100 / 100	212 ms	96084 KiB

fireworks

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 3e5 + 11, inf = 1000111222;


vector <pii> edge[max_n];

int n, m;

ll ans = 0;

bool del[max_n];

inline bool dfs (int v, int p = -1, bool gg = false) {
    bool ok = v >= n || gg;
    bool there = v >= n;
    for (auto [to, len] : edge[v]) {
        if (to == p) {
            continue;
        }
        if (dfs(to, v, ok)) {
            there = true;
            if (ok) {
                ans += len;
            }
        }
    }
    if (v >= n && !gg) {
        del[v] = true;
    }
    return there;
}

bool need[max_n];

priority_queue <ll> q[max_n];
ll b[max_n];
int k[max_n];

inline void solve (int v, int p = -1) {
    int mx = -1, big = -1, L = -1;
    for (auto [to, len] : edge[v]) {
        if (to == p) {
            continue;
        }
        if (del[to]) {
            need[v] = true;
            if (umax(mx, 0)) {
                big = to;
                L = len;
            }
        }
        else {
            solve(to, v);
            if (!need[to]) {
                continue;
            }
            need[v] = true;
            if (umax(mx, len(q[to]))) {
                big = to;
                L = len;
            }
        }
    }
    if (!need[v]) {
        return;
    }
    assert(big != -1);
    {
        int to = big, len = L;
        if (del[to]) {
            b[v] -= len;
            ++k[v];
            q[v].push(len);
            q[v].push(len);
        } else {
            int to_del = k[to] - 1;
            ll s = 0;
            for (int i = 0; i < to_del; i++) {
                s += q[to].top();
                q[to].pop();
            }
            ll a2 = q[to].top() + len;
            q[to].pop();
            ll a1 = q[to].top() + len;
            q[to].pop();
            q[v].swap(q[to]);
            q[v].push(a1);
            q[v].push(a2);
            b[v] += b[to] - len + s;
            ++k[v];
        }
    }
    for (auto [to, len] : edge[v]) {
        if (to == p || to == big) {
            continue;
        }
        if (del[to]) {
            b[v] -= len;
            ++k[v];
            q[v].push(len);
            q[v].push(len);
        }
        else {
            if (!need[to]) {
                continue;
            }
            int to_del = k[to] - 1;
            ll s = 0;
            for (int i = 0; i < to_del; i++) {
                s += q[to].top();
                q[to].pop();
            }
            ll a2 = q[to].top() + len;
            q[to].pop();
            ll a1 = q[to].top() + len;
            q[to].pop();
            while (!q[to].empty()) {
                q[v].push(q[to].top());
                q[to].pop();
            }
            q[v].push(a1);
            q[v].push(a2);
            b[v] += b[to] - len + s;
            ++k[v];
        }
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1, p, c; i < n + m; i++) {
        cin >> p >> c;
        --p;
        edge[p].pb({i, c});
        edge[i].pb({p, c});
    }
    dfs(0);
    solve(0);
    while (k[0] > 0) {
        b[0] += q[0].top();
        q[0].pop();
        --k[0];
    }
    assert(!q[0].empty());
    cout << b[0] + ans << '\n';
}

Compilation message (stderr)

fireworks.cpp: In function 'bool dfs(int, int, bool)':
fireworks.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [to, len] : edge[v]) {
      |               ^
fireworks.cpp: In function 'void solve(int, int)':
fireworks.cpp:86:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for (auto [to, len] : edge[v]) {
      |               ^
fireworks.cpp:138:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for (auto [to, len] : edge[v]) {
      |               ^

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