Submission #794446

#	Time	Username	Problem	Language	Result	Execution time	Memory
794446		WLZ	Fireworks (APIO16_fireworks)	C++17	100 / 100	211 ms	80324 KiB

fireworks

#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>());
  c[1] = 0;
  int rep = dfs(1);
  while (a[1] > 0) {
    b[1] += pq[rep].top(); pq[rep].pop();
    a[1]--;
  }
  cout << b[1] << '\n';
}

Compilation message (stderr)

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]);
      |   ^~~~~

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