Submission #234395

#	Time	Username	Problem	Language	Result	Execution time	Memory
234395		AlexLuchianov	Fireworks (APIO16_fireworks)	C++14	100 / 100	539 ms	69752 KiB

fireworks

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

class Slope{
public:
  ll a;
  ll b;
  std::priority_queue<ll> pq;
  Slope(){
    a = b = 0;
  }
  int size(){
    return pq.size();
  }
  ll top(){
    return pq.top();
  }
  void pop(){
    pq.pop();
  }
  void push(ll val){
    pq.push(val);
  }

  void flatten(){
    while(1 < a){
      a--;
      b += pq.top();
      pq.pop();
    }
  }

  void shift(ll val){
    assert(a == 1);
    ll p1 = pq.top();
    pq.pop();
    ll p2 = pq.top();
    pq.pop();
    pq.push(p2 + val);
    pq.push(p1 + val);
    b -= val;
  }
};

void _add(Slope &x, Slope &y){
  if(x.size() < y.size())
    std::swap(x, y);
  x.a += y.a;
  x.b += y.b;
  while(0 < y.size()){
    x.push(y.top());
    y.pop();
  }
}

int const nmax = 300000;
std::vector<int> g[1 + nmax];
int upper[1 + nmax];

Slope dp[1 + nmax];

void dfs(int node){
  if(g[node].size() == 0){
    dp[node].push(0);
    dp[node].push(0);
    dp[node].a = 1;
    dp[node].b = 0;
  }
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    dfs(to);
    _add(dp[node], dp[to]);
  }

  dp[node].flatten();
  dp[node].shift(upper[node]);
}

int main()
{
  int n, m;
  std::cin >> n >> m;
  for(int i = 2;i <= n + m; i++){
    int far;
    std::cin >> far >> upper[i];
    g[far].push_back(i);
  }
  dfs(1);
  std::cout << dp[1].top() + dp[1].b;
  return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

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