This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a);)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) static_cast<int>((x).size())
template <class T>
bool uin(T& a, const T& b) {
return a > b ? a = b, true : false;
}
template <class T>
bool uax(T& a, const T& b) {
return a < b ? a = b, true : false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
swap(n, m);
n += m;
vector<int> p(n), c(n);
rep(i, 1, n) {
cin >> p[i] >> c[i];
--p[i];
}
struct node {
int a;
ll b;
priority_queue<ll> q;
node() : a{0}, b{0} {}
node(int x) : a{1}, b{-x}, q{{}, {x, x}} {}
void merge(node& o) {
a += o.a;
b += o.b;
if (sz(q) < sz(o.q)) swap(q, o.q);
while (!o.q.empty()) {
q.push(o.q.top());
o.q.pop();
}
}
};
vector<node> data(n);
per(i, m, n) {
data[i] = node(c[i]);
data[p[i]].merge(data[i]);
}
per(i, 1, m) {
const auto x = c[i];
auto& [a, b, q] = data[i];
while (a > 1) {
--a;
b += q.top();
q.pop();
}
const auto one = q.top();
q.pop();
const auto zero = q.top();
q.pop();
q.push(one + x);
q.push(zero + x);
b -= x;
data[p[i]].merge(data[i]);
}
auto& [a, b, q] = data[0];
while (a > 0) {
--a;
b += q.top();
q.pop();
}
cout << b << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |