Submission #1106019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106019		LaviniaTornaghi	Fireworks (APIO16_fireworks)	C++14	100 / 100	143 ms	75704 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

#define int i64

typedef long long i64;

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int N, M; cin >> N >> M;

  vector<vector<int>> adj(N);
  vector<int> t(N + M);

  for (int i = 1; i < N + M; i++) {
    int p; cin >> p >> t[i];
    adj[p - 1].push_back(i);
  }

  auto dfs = [&](auto &&dfs, int node) {
    priority_queue<i64> q;
    if (node >= N) {
      q.push(t[node]);
      q.push(t[node]);
      return q;
    }

    for (auto child: adj[node]) {
      priority_queue<i64> cq = dfs(dfs, child);
      
      if (q.size() < cq.size())
      	swap(q, cq);
      while (!cq.empty()) {
        q.push(cq.top());
        cq.pop();
      }
    }
    for (int i = 0; i < adj[node].size() - 1; i++) q.pop();

    i64 x1 = q.top(); q.pop();
    i64 x0 = q.top(); q.pop();

    q.push(x0 + t[node]);
    q.push(x1 + t[node]);

    return q;
  };

  priority_queue<i64> q = dfs(dfs, 0);
  vector<i64> slope_changes;
  while (!q.empty()) {
    int x = q.top(); q.pop();
    slope_changes.push_back(x);
  }

  reverse(slope_changes.begin(), slope_changes.end());
  int curr_slope = 1 - (int)slope_changes.size();
  i64 last_point = 0;
  i64 curr_value = accumulate(t.begin(), t.end(), 0LL);
  i64 best_value = curr_value;

  for (auto x: slope_changes) {
    curr_value += curr_slope * (x - last_point);
    best_value = min(best_value, curr_value);

    last_point = x;
    curr_slope++;
  }

  cout << best_value << '\n';
}

Compilation message (stderr)

fireworks.cpp: In instantiation of 'main()::<lambda(auto:1&&, i64)> [with auto:1 = main()::<lambda(auto:1&&, i64)>&; i64 = long long int]':
fireworks.cpp:49:37:   required from here
fireworks.cpp:38:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < adj[node].size() - 1; i++) q.pop();
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~

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