Submission #727608

#TimeUsernameProblemLanguageResultExecution timeMemory
727608OzyFireworks (APIO16_fireworks)C++17
100 / 100
313 ms80356 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define lli long long int #define pll pair<lli,lli> #define MAX 300000 //para los hijos #define des first #define w second struct x { multiset<lli> s; lli pend; lli ord; }; lli n,m,a,b,res; vector<pll> hijos[MAX+2]; lli si[MAX+2]; multiset<lli>::iterator it; x solve(lli pos,lli dis) { x slope; slope.s.clear(); if (pos > n) { // es un explosivo slope.s.insert(dis); slope.s.insert(dis); slope.pend = 1; slope.ord = -dis; return slope; } slope.pend = 0; slope.ord = 0; for (auto h : hijos[pos]) { if (si[h.des] == 0) continue; x act = solve(h.des, h.w); // aqui mergeo if (act.s.size() > slope.s.size()) { swap(act.s, slope.s); swap(act.pend, slope.pend); swap(act.ord, slope.ord); } for (auto k : act.s) slope.s.insert(k); slope.pend += act.pend; slope.ord += act.ord; } while (slope.pend > 1) { it = slope.s.end(); it--; slope.ord += (*it); slope.s.erase(it); slope.pend--; } // aqui hago la magia del slope slope.ord -= dis; it = slope.s.end(); it--; lli a = (*it) + dis; slope.s.erase(it); it = slope.s.end(); it--; lli b = (*it) + dis; slope.s.erase(it); slope.s.insert(a); slope.s.insert(b); return slope; } void chequeo(lli pos) { if (pos > n) {si[pos] = 1; return;} for (auto h : hijos[pos]) { chequeo(h.des); si[pos] = (si[pos]|si[h.des]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; rep(i,2,n) { cin >> a >> b; hijos[a].push_back({i,b}); } res = 0; rep(i,n+1,n+m) { cin >> a >> b; if (a > n) res += b; else hijos[a].push_back({i,b}); } //eliminar aristas que no tengan ningún explosivo debajo chequeo(1); x fin = solve(1,0); it = fin.s.end(); it--; fin.ord += (*it); res += fin.ord; cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...