Submission #1086606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086606		Icelast	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	478 ms	208392 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;
vector<int> find_cycle(vector<vector<int>> &adj){
    int n = adj.size()-1;
    vector<int> cyc(n+1, 0);
    vector<int> vis(n+1, 0), pa(n+1, -1);
    auto dfs = [&](auto dfs, int u) -> void{
        vis[u] = 1;
        for(int v : adj[u]){

            if(vis[v] == 1){
                //cycle found
                int t = u;
                while(t != v){
                    cyc[t] = v;
                    t = pa[t];
                }
                cyc[v] = v;
            }
            if(!vis[v]){
                pa[v] = u;
                dfs(dfs, v);
            }
        }
        vis[u] = 2;
    };
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        dfs(dfs, i);
    }
    return cyc;
}
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1), adj_rev(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_rev[v].push_back(i);
    }
    vector<int> cyc = find_cycle(adj);
    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 || cyc[node]) 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), res(n+1);

    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(int v : adj_rev[u]){
            if(v == p || cyc[v]) continue;
            dfs(dfs, v, u);
            add(dp[u], dp[v]);
        }
        fix(u, dp[u], h[u], c[u]);
    };
    for(int i = 1; i <= n; i++){
        if(cyc[i]){
            dfs(dfs, i, i);
            add(res[cyc[i]], dp[i]);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll pf = 0, mn = INF;
        if(res[i].size() == 0) mn = 0;
        for(auto it : res[i]){
            pf += it.second;
            mn = min(mn, pf);
        }
        ans += mn;
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void solve()':
worst_reporter2.cpp:41:9: warning: unused variable 'root' [-Wunused-variable]
   41 |     int root = 1;
      |         ^~~~

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