Submission #950185

#	Time	Username	Problem	Language	Result	Execution time	Memory
950185		abczz	Fireworks (APIO16_fireworks)	C++14	100 / 100	336 ms	89944 KiB

fireworks

#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

priority_queue<ll> pq[300000];
vector <ll> V;
vector <array<ll, 2> > adj[300000];
ll n, m, f, k, s, p, P[300000];

void dfs(ll u) {
  ll mx = 0, id = -1, z;
  for (auto [v, x] : adj[u]) {
    dfs(v);
    if (pq[v].size() > mx) {
      mx = pq[v].size();
      id = v, z = x;
    }
  }
  if (id != -1) {
    swap(pq[u], pq[id]);
    auto a = pq[u].top();
    pq[u].pop();
    auto b = pq[u].top();
    pq[u].pop();
    pq[u].push(a+z);
    pq[u].push(b+z);
  }
  for (auto [v, x] : adj[u]) {
    if (v != id) {
      auto a = pq[v].top();
      pq[v].pop();
      auto b = pq[v].top();
      pq[v].pop();
      pq[v].push(a+x);
      pq[v].push(b+x);
      while (!pq[v].empty()) {
        auto y = pq[v].top();
        pq[v].pop();
        pq[u].push(y);
      }
    }
  }
  for (int i=1; i<adj[u].size(); ++i) {
    pq[u].pop();
  }
  if (adj[u].empty()) {
    for (int i=0; i<2; ++i) {
      pq[u].push(0);
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i=1; i<n+m; ++i) {
    cin >> P[i] >> k;
    s += k;
    --P[i];
    adj[P[i]].push_back({i, k});
  }
  dfs(0);
  while (!pq[0].empty()) {
    auto u = pq[0].top();
    V.push_back(u);
    pq[0].pop();
  }
  V.push_back(0);
  for (ll i=0; i+1<V.size(); ++i) {
    s -= (V[i]-V[i+1]) * i;
  }
  cout << s << '\n';
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int)':
fireworks.cpp:18:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |   for (auto [v, x] : adj[u]) {
      |             ^
fireworks.cpp:20:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |     if (pq[v].size() > mx) {
      |         ~~~~~~~~~~~~~^~~~
fireworks.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |   for (auto [v, x] : adj[u]) {
      |             ^
fireworks.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i=1; i<adj[u].size(); ++i) {
      |                 ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:74:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (ll i=0; i+1<V.size(); ++i) {
      |                ~~~^~~~~~~~~

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