oj.uz

Submission #234394

# Submission time Handle Problem Language Result Execution time Memory
234394 2020-05-24T06:55:53 Z AlexLuchianov Fireworks (APIO16_fireworks) C++14
0 / 100
 17 ms 21504 KB 
#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);
  dp[1].pop();
  std::cout << dp[1].top() + dp[1].b;
  return 0;
}

Compilation message

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21504 KB Output is correct
2 Correct 16 ms 21504 KB Output is correct
3 Correct 17 ms 21504 KB Output is correct
4 Correct 17 ms 21504 KB Output is correct
5 Incorrect 16 ms 21504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 21504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21504 KB Output is correct
2 Correct 16 ms 21504 KB Output is correct
3 Correct 17 ms 21504 KB Output is correct
4 Correct 17 ms 21504 KB Output is correct
5 Incorrect 16 ms 21504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21504 KB Output is correct
2 Correct 16 ms 21504 KB Output is correct
3 Correct 17 ms 21504 KB Output is correct
4 Correct 17 ms 21504 KB Output is correct
5 Incorrect 16 ms 21504 KB Output isn't correct
6 Halted 0 ms 0 KB -