oj.uz

답안 #794444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794444 2023-07-26T14:26:27 Z WLZ Fireworks (APIO16_fireworks) C++17
0 / 100
 1 ms 328 KB 
#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]);
      |   ^~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 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 -