제출 #494696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494696		PixelCat	Fireworks (APIO16_fireworks)	C++14	0 / 100	12 ms	14572 KiB

fireworks

/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */
/*      Nightshade221#0341 was here lol      */
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1000000000000000ll)  // 1e15
#define EPS (1e-6)

#ifdef NYAOWO
#include "debug.h"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p /= 2;
        b = b * b % mod;
    }
    return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64
// rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int a, b;
    priority_queue<int> pq;
    Node() : a(0), b(0), pq() {}
    void operator+=(Node &nd) {
        a += nd.a;
        b += nd.b;
        // cout << "called " << sz(pq) << " " << sz(nd.pq)
        //      << "\n";
        if (sz(pq) < sz(nd.pq)) pq.swap(nd.pq);
        while (sz(nd.pq)) {
            pq.emplace(nd.pq.top());
            nd.pq.pop();
        }
        // cout << "finished " << sz(pq) << " " << sz(nd.pq)
        //      << "\n";
        while (a > 1) {
            a--;
            b += pq.top();
            pq.pop();
        }
    }
} nd[300030];

int p[300030];
int c[300030];

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n, m;
    cin >> n >> m;
    For(i, 2, n + m) cin >> p[i] >> c[i];
    Forr(i, n + m, n + 1) {
        nd[i].a = 1;
        nd[i].b = -c[i];
        nd[i].pq.emplace(c[i]);
        nd[i].pq.emplace(c[i]);
        nd[p[i]] += nd[i];
    }
    Forr(i, n, 2) {
        // debug(i, sz(nd[i].pq));
        int r = nd[i].pq.top();
        nd[i].pq.pop();
        int l = nd[i].pq.top();
        nd[i].pq.pop();
        // debug(l, r);
        nd[i].pq.emplace(r + c[i]);
        nd[i].pq.emplace(l + c[i]);
        nd[i].b -= c[i];
        nd[p[i]] += nd[i];
    }
    while (nd[1].a > 0) {
        nd[1].a--;
        nd[1].b += nd[1].pq.top();
        nd[1].pq.pop();
    }
    cout << nd[1].b << "\n";
    return 0;
}

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