Submission #1153035

#TimeUsernameProblemLanguageResultExecution timeMemory
1153035vladiliusFireworks (APIO16_fireworks)C++20
0 / 100
4 ms764 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; int f = n + m; vector<ll> p(f + 1); vector<int> g[f + 1]; for (int i = 2; i <= n; i++){ int x, w; cin>>x>>w; g[x].pb(i); p[i] = p[x] + w; } vector<bool> d(f + 1); for (int i = 1; i <= n; i++) d[i] = 1; for (int i = n + 1; i <= f; i++){ int x, w; cin>>x>>w; g[x].pb(i); p[i] = p[x] + w; if (x > n){ d[i] = 1; } } ll out = 0; function<void(int)> dfs = [&](int v){ for (int i: g[v]){ dfs(i); out += abs(p[i] - p[v]); } }; ll mx = 0; for (int i = 1; i <= f; i++) mx = max(mx, p[i]); const ll A = mx; vector<ll> all; vector<vector<ll>> t(f + 1, vector<ll>(A + 1)); for (int i = 1; i <= n; i++){ for (int j = 1; j <= A; j++){ t[i][j] = 0; } } for (int i = n + 1; i <= f; i++){ if (!d[i]){ dfs(i); for (int j = 1; j <= A; j++){ t[i][j] = abs(j - p[i]); } } } function<void(int)> fill = [&](int v){ if (!d[v]) return; for (int i: g[v]){ fill(i); } for (int x = 1; x <= A; x++){ for (int i: g[v]){ ll mn = 1e18; for (int a = 1; a <= A; a++){ mn = min(mn, t[i][a] + abs(a - x)); } t[v][x] += mn; } } }; fill(1); ll mn = 1e18; for (int x = 1; x <= A; x++) mn = min(mn, t[1][x]); out += mn; cout<<out<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...