Submission #1289744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289744		lmquan	Fireworks (APIO16_fireworks)	C++20	100 / 100	236 ms	87320 KiB

fireworks

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kMaxNM = 300005;

int n, m;
vector<pair<int, int>> children[kMaxNM];

struct SlopeTrick {
  long long first_value, initial_slope;
  multiset<long long> slope_changing_points;

  SlopeTrick() { first_value = initial_slope = 0; }
};

SlopeTrick dp[kMaxNM];

void DFS(int u) {
  for (auto i : children[u]) {
    int v = i.first, w = i.second;
    if (v <= n) {
      DFS(v);
      dp[v].first_value += w;

      dp[v].initial_slope = min(dp[v].initial_slope, -1LL);
      
      long long x = *dp[v].slope_changing_points.rbegin() + w;
      long long y = *(--(--dp[v].slope_changing_points.end())) + w;
      dp[v].slope_changing_points.erase(--dp[v].slope_changing_points.end());
      dp[v].slope_changing_points.erase(--dp[v].slope_changing_points.end());
      dp[v].slope_changing_points.insert(x);
      dp[v].slope_changing_points.insert(y);
    } else {
      dp[v].first_value = w;
      dp[v].initial_slope = -1;
      dp[v].slope_changing_points.insert(w);
      dp[v].slope_changing_points.insert(w);
    }

    dp[u].first_value += dp[v].first_value;
    dp[u].initial_slope += dp[v].initial_slope;

    if (dp[u].slope_changing_points.size() < dp[v].slope_changing_points.size()) {
      swap(dp[u].slope_changing_points, dp[v].slope_changing_points);
    }
    for (long long e : dp[v].slope_changing_points) {
      dp[u].slope_changing_points.insert(e);
    }
    dp[v].slope_changing_points.clear();
  }

  while (dp[u].initial_slope + dp[u].slope_changing_points.size() >= 2) {
    dp[u].slope_changing_points.erase(--dp[u].slope_changing_points.end());
  }
}

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 2; i <= n + m; i++) {
    int p, c;
    cin >> p >> c;
    children[p].push_back({i, c});
  }

  int root = 1;
  DFS(root);

  long long result = dp[root].first_value, d = dp[root].initial_slope, prev = 0;
  for (long long i : dp[root].slope_changing_points) {
    if (d == 1) {
      break;
    }
    result += (i - prev) * d;
    prev = i, d++;
  }

  cout << result;

  return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:59:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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