#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "templates/debug.h"
#else
#define debug(...) 0
#endif
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define eb emplace_back
#define pb push_back
#define MP make_pair
#define MT make_tuple
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) x.size()
using ll = long long;
using ull = unsigned ll;
using lll = __int128_t;
using ulll = __uint128_t;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
template<typename T> using max_pq = priority_queue<T>;
template<typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
template<typename T> void cmax(T &a, const T &b) { a = max(a, b); }
template<typename T> void cmin(T &a, const T &b) { a = min(a, b); }
const int INF = 0x3f3f3f3f;
const ll LINF = (ll) 1e18;
const double DINF = 1.0 / 0.0;
const double pi = acos(-1);
const double EPS = 1e-9;
void solve(int current_case);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
for (int q = 1; q <= t; q++) solve(q);
return 0;
}
int n, m;
vi p, c;
vll a, b;
vector< max_pq<ll> > pq;
vector<vi> g;
int dfs(int u) {
if (g[u].empty()) {
pq[u].push(c[u]); pq[u].push(c[u]);
a[u] = 1; b[u] = -c[u];
debug(u, a[u], b[u], pq[u]);
return u;
}
int rep = u;
a[u] = b[u] = 0;
for (auto &v : g[u]) {
int other = dfs(v);
a[u] += a[v]; b[u] += b[v];
if (SZ(pq[other]) > SZ(pq[rep])) swap(rep, other);
while (!pq[other].empty()) {
pq[rep].push(pq[other].top());
pq[other].pop();
}
}
while (a[u] > 1) {
b[u] += pq[rep].top(); pq[rep].pop();
a[u]--;
}
ll lx = pq[rep].top(); pq[rep].pop(); // 0 -> 1
ll ly = pq[rep].top(); pq[rep].pop(); // -1 -> 0
pq[rep].push(lx + c[u]); pq[rep].push(ly + c[u]);
b[u] -= c[u];
debug(u, a[u], b[u], pq[rep]);
return rep;
}
void solve(int current_case) {
cin >> n >> m;
g.resize(n + m + 1);
p.resize(n + m + 1); c.resize(n + m + 1);
rep(i, 2, n + m + 1) {
cin >> p[i] >> c[i];
g[p[i]].pb(i);
}
a.resize(n + m + 1); b.resize(n + m + 1);
pq.assign(n + m + 1, max_pq<ll>());
int rep;
rep(i, 2, n + m + 1) {
if (p[i] == 1) {
rep = dfs(i);
while (a[i] > 0) {
b[i] += pq[rep].top(); pq[rep].pop();
a[i]--;
}
cout << b[i] << '\n';
return;
}
}
}
Compilation message
fireworks.cpp: In function 'int dfs(int)':
fireworks.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define debug(...) 0
| ^
fireworks.cpp:60:5: note: in expansion of macro 'debug'
60 | debug(u, a[u], b[u], pq[u]);
| ^~~~~
fireworks.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define debug(...) 0
| ^
fireworks.cpp:82:3: note: in expansion of macro 'debug'
82 | debug(u, a[u], b[u], pq[rep]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
