Submission #386040

#	Time	Username	Problem	Language	Result	Execution time	Memory
386040		MiricaMatei	Fireworks (APIO16_fireworks)	C++14	100 / 100	231 ms	51872 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

const int MAXN =  300005;

vector<int>G[MAXN];
priority_queue<long long>pq[MAXN];
long long a[MAXN], b[MAXN];
int c[MAXN];

int main() {

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 2; i <= n + m; ++i) {
    int p;
    scanf("%d%d", &p, &c[i]);
    G[p].push_back(i);
  }

  for (int i = n + 1; i <= n + m; ++i) {
    pq[i].push(c[i]);
    pq[i].push(c[i]);
    a[i] = 1;
    b[i] = -c[i];
  }

  for (int i = n; i >= 1; --i) {
    for (auto it:G[i]) {
      if (pq[i].size() < pq[it].size())
        swap(pq[i], pq[it]);
      while (!pq[it].empty()) {
        pq[i].push(pq[it].top());
        pq[it].pop();
      }
      a[i] += a[it];
      b[i] += b[it];
    }
    while (a[i] > 1) {
      long long x = pq[i].top();
      a[i]--;
      b[i] += x;
      pq[i].pop();
    }

    b[i] -= c[i];
    long long x1 = pq[i].top();
    pq[i].pop();
    long long x0 = pq[i].top();
    pq[i].pop();
    x1 += c[i];
    x0 += c[i];
    pq[i].push(x0);
    pq[i].push(x1);
  }

  while (a[1] > 0) {
    long long x = pq[1].top();
    a[1]--;
    b[1] += x;
    pq[1].pop();
  }

  printf("%lld\n", b[1]);

  return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     scanf("%d%d", &p, &c[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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