Submission #997197

#	Time	Username	Problem	Language	Result	Execution time	Memory
997197		snpmrnhlol	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	327 ms	80724 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5;
ll v[N],v2[N],cost[N];
vector <ll> e[N];
ll vis[N];
vector <ll> chain;
map <ll,ll> costs[N];
map <ll,ll> res;
map <ll,ll> sv;
void dfs(ll node, ll p){
    //cout<<node<<' '<<p<<'\n';
    vis[node] = 2;
    for(auto i:e[node]){
        if(i == p || vis[i] == 2)continue;
        dfs(i,node);
        if(costs[node].size() < costs[i].size()){
            swap(costs[node],costs[i]);
        }
        for(auto j:costs[i]){
            costs[node][j.first]+=j.second;
        }
        costs[i].clear();
    }
    if(p != -1){
        ll x = cost[node];
        while(x > 0){
            auto it = costs[node].lower_bound(v2[node]);
            if(it == costs[node].begin())break;
            it = prev(it);
            ll nr = min(x,it->second);
            x-=nr;
            it->second-=nr;
            if(it->second == 0)costs[node].erase(it->first);
        }
        costs[node][v2[node]]+=cost[node];
    }
}
int main(){
    ll n;
    ll ans2 = 0,sum = 0;
    cin>>n;
    for(ll i = 0;i < n;i++){
        cin>>v[i]>>v2[i]>>cost[i];
        sum+=cost[i];
        v[i]--;
        e[v[i]].push_back(i);
    }
    for(ll i = 0;i < n;i++){
        if(vis[i])continue;
        chain.clear();
        ll nr = i;
        while(vis[nr] == 0){
            vis[nr] = 1;
            nr = v[nr];
        }
        while(vis[nr] == 1){
            chain.push_back(nr);
            vis[nr] = 2;
            nr = v[nr];
        }
        res.clear();
        sv.clear();
        ll ans = 0;
        for(auto j:chain){
            dfs(j,-1);
            for(auto k:costs[j]){
                res[k.first]+=k.second;
            }
            sv[v2[j]]+=cost[j];
        }
        if(!res.empty()){
            ll sum2 = 0;
            for(auto k = prev(res.end());1;k--){
                sum2+=k->second;
                k->second = sum2;
                if(k == res.begin())break;
            }
            ans = max(ans,sum2);
            for(auto k = prev(sv.end());1;k--){
                auto it = res.lower_bound(k->first);
                if(it == res.end()){
                    ans = max(ans,k->second);
                }else{
                    ans = max(ans,k->second + it->second);
                }
                if(k == sv.begin())break;
            }
        }else{
            for(auto k:sv){
                ans = max(ans,k.second);
            }
        }
        //cout<<ans<<'\n';
        ans2+=ans;
    }
    cout<<sum - ans2<<'\n';
    return 0;
}

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