Submission #1000021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000021		kunzaZa183	Fireworks (APIO16_fireworks)	C++17	100 / 100	218 ms	105676 KiB

fireworks

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

const int maxn = 300000;

vector<pair<int, int>> adjlist[maxn];

pair<int, multiset<int> *> pimi(int cur, int val) {
  vector<multiset<int> *> vm;
  int income = 0;
  for (auto a : adjlist[cur]) {
    auto b = pimi(a.first, a.second);
    income += b.first;
    vm.push_back(b.second);
  }
  multiset<int> *maxi = new multiset<int>;
  if (vm.empty()) {
    maxi->insert(val), maxi->insert(val);
    return {1, maxi};
  }
  for (auto a : vm)
    if (a->size() > maxi->size()) maxi = a;
  for (auto a : vm)
    if (a != maxi)
      for (auto b : *a) maxi->insert(b);
  while (income + 1 < maxi->size()) maxi->erase(maxi->find(*maxi->rbegin()));
  int second = *maxi->rbegin();
  maxi->erase(maxi->find(*maxi->rbegin()));
  int first = *maxi->rbegin();
  maxi->erase(maxi->find(*maxi->rbegin()));
  first += val, second += val;
  maxi->insert(first), maxi->insert(second);
  return {income, maxi};
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;
  int sum = 0;
  for (int i = 0; i < n + m - 1; i++) {
    int dist, c;
    cin >> dist >> c;
    sum += c;
    adjlist[dist - 1].emplace_back(i + 1, c);
  }
  auto [a, b] = pimi(0, 0);
  b->erase(b->find(*b->rbegin()));
  int last = 0;
  int slope = a;
  for (auto x : *b) {
    sum -= (x - last) * slope;
    slope--;
    last = x;
  }
  cout << sum << "\n";
}

Compilation message (stderr)

fireworks.cpp: In function 'std::pair<long long int, std::multiset<long long int>*> pimi(long long int, long long int)':
fireworks.cpp:27:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   while (income + 1 < maxi->size()) maxi->erase(maxi->find(*maxi->rbegin()));
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~

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