Submission #959960

#TimeUsernameProblemLanguageResultExecution timeMemory
959960Trisanu_DasFireworks (APIO16_fireworks)C++17
55 / 100
2067 ms23352 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; vector<pli> adj[300001]; const i64 inf = numeric_limits<i64>::max() / 3; inline i64 ab(i64 x) { return x > 0 ? x : -x; } class slope { public: priority_queue<i64> bp; i64 sac, fz; slope() { sac = 0; fz = 0; } void push(i64 x) { fz += x; if (bp.empty()) { bp.push(x); bp.push(x); ++sac; return; } while (bp.size() > sac + 1) bp.pop(); auto m1 = bp.top(); bp.pop(); auto m2 = bp.top(); bp.pop(); bp.push(m1 + x); bp.push(m2 + x); } }; void mer(slope* s1, slope* s2) { s1->fz += s2->fz; s1->sac += s2->sac; while (!s2->bp.empty()) s1->bp.push(s2->bp.top()), s2->bp.pop(); delete s2; } slope* solve(int h, int p = -1) { slope* ret = new slope(); for (auto [t, wf] : adj[h]) { if (t == p) continue; auto chslp = solve(t, h); chslp->push(wf); mer(ret, chslp); } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; for (int i = 2; i <= N + M; i++) { i64 j, w; cin >> j >> w; adj[i].emplace_back(j, w); adj[j].emplace_back(i, w); } auto res = *solve(1); vector<i64> bp; while (!res.bp.empty()) bp.emplace_back(res.bp.top()), res.bp.pop(); reverse(bp.begin(), bp.end()); for (int i = 0; i < res.sac; i++) res.fz -= bp[i]; cout << res.fz << '\n'; }

Compilation message (stderr)

fireworks.cpp: In member function 'void slope::push(i64)':
fireworks.cpp:37:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'i64' {aka 'long long int'} [-Wsign-compare]
   37 |         while (bp.size() > sac + 1) bp.pop();
      |                ~~~~~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...