This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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()));
| ~~~~~~~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |