oj.uz

답안 #494696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494696 2021-12-16T02:24:50 Z PixelCat Fireworks (APIO16_fireworks) C++14
0 / 100
 12 ms 14572 KB 
/*       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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Incorrect 11 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Incorrect 11 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Incorrect 11 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -