Submission #1261646

#TimeUsernameProblemLanguageResultExecution timeMemory
1261646ngmtuanFireworks (APIO16_fireworks)C++20
0 / 100
3 ms7492 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define sz(x) ((int)(x).size()) #define all(x) ((x).begin(), (x).end()) const int N = 3e5 + 5; int n, m; int p[N], c[N]; vector<int> g[N]; struct slopes { ll a, b; deque<ll> xs; }; slopes dfs(int u) { if (u > n) { return {-1, 0, {0, 0}}; } slopes h; for (int v : g[u]) { auto f = dfs(v); while (f.a < -1) f.a++, f.b -= f.xs.front(), f.xs.pop_front(); while (f.a + f.xs.size() > 1) f.xs.pop_back(); for (auto &x : f.xs) { x += c[v]; } f.b -= f.a * c[v]; h.a += f.a, h.b += f.b; for (ll x : f.xs) h.xs.push_back(x); } sort(h.xs.begin(), h.xs.end()); return h; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 2; i <= n + m; i++) { cin >> p[i] >> c[i]; g[p[i]].push_back(i); } auto res = dfs(1); for (ll x : res.xs) { res.b -= x; res.a++; if (res.a == 0) { cout << res.b << endl; return 0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...