Submission #109850

#TimeUsernameProblemLanguageResultExecution timeMemory
109850Alexa2001Fireworks (APIO16_fireworks)C++17
7 / 100
18 ms14520 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int Nmax = 6e5 + 5; const ll inf = 1e18; vector<int> v[Nmax]; ll opt[Nmax], A[Nmax], B[Nmax]; int up[Nmax]; int n, m; ll moove(ll x, ll l, ll r) { if(x < l) return l - x; if(x > r) return x - r; return 0; } void dfs(int node) { if(v[node].empty()) { opt[node] = 0; A[node] = up[node]; B[node] = up[node]; return; } for(auto son : v[node]) dfs(son); map<ll,int> change; for(auto son : v[node]) { change[0] -= 1; change[A[son]] += 1; change[B[son]] += 1; } int sum = 0; ll L = -1, R = -1; for(auto &it : change) { sum += it.second; it.second = sum; if(it.second >= 0 && L == -1) L = it.first; if(it.second > 0 && R == -1) R = it.first; } A[node] = L; B[node] = R; for(auto son : v[node]) opt[node] += opt[son] + moove(L, A[son], B[son]); A[node] += up[node]; B[node] += up[node]; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); int i, x; cin >> n >> m; n += m; for(i=2; i<=n; ++i) { cin >> x >> up[i]; v[x].push_back(i); } dfs(1); cout << opt[1] << '\n'; 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...