/* 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) {
nd[1].a--;
nd[1].b += nd[1].pq.top();
nd[1].pq.pop();
}
cout << nd[1].b << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14648 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14648 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14648 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
