Submission #1086402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086402		Icelast	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	409 ms	190544 KiB

worst_reporter2

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1);
    vector<ll> h(n+1), c(n+1);
    int root = 1;
    ll sumc = 0;
    for(int i = 1; i <= n; i++){
        int v;
        cin >> v >> h[i] >> c[i];
        sumc += c[i];
        adj[i].push_back(v);
        adj[v].push_back(i);
    }
    auto add = [&](map<ll, ll> &u, map<ll, ll> &v){
        if(u.size() < v.size()) swap(u, v);
        for(auto it : v){
            ll h = it.first, c = it.second;
            u[h] += c;
        }
    };
    auto fix = [&](int node, map<ll, ll> &u, ll h, ll d){
        u[h] -= d;
        u[h+1] += d;
        u[0] += d;
        if(u[h] >= 0 || node == root) return;
        d = -u[h];
        u[h] = 0;
        auto it = u.lower_bound(h);
        while(it != u.begin()){
            it = prev(it);
            if(it->second <= d){
                d -= it->second;
                it = u.erase(it);
            }else{
                it->second -= d;
                break;
            }
        }
    };
    vector<map<ll, ll>> dp(n+1);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(int v : adj[u]){
            if(v == p) continue;
            dfs(dfs, v, u);
            add(dp[u], dp[v]);
        }
        fix(u, dp[u], h[u], c[u]);
    };
    dfs(dfs, 1, 1);
    ll ans = INF, res = 0;
    for(auto it : dp[1]){
        res += it.second;
        ans = min(ans, res);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21