Submission #1136296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136296		byunjaewoo	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	79 / 100	885 ms	589824 KiB

worst_reporter2

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=200010;
int n, ans, a[N], h[N], c[N];
bool chk[N];
vector<int> adj[N];

void Merge(map<int, int> &a, map<int, int> &b) {
    if(a.size()<b.size()) swap(a, b);
    for(auto [i, j]:b) a[i]+=j;
    b.clear();
}

map<int, int> dfs(int curr, int ban, int root) {
    chk[curr]=true;
    map<int, int> ret;
    for(int next:adj[curr]) if(next!=ban) {
        map<int, int> tmp=dfs(next, ban, root);
        Merge(ret, tmp);
    }
    ret[h[curr]]+=c[curr];
    if(curr==root) {
        ret[h[curr]+1]-=c[curr];
        return ret;
    }
    int tmp=c[curr];
    while(true) {
        auto p=ret.upper_bound(h[curr]);
        if(p==ret.end()) break;
        if((*p).second>=tmp) {
            ret[(*p).first]-=tmp; break;
        }
        tmp-=(*p).second, ret.erase(p);
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i]>>h[i]>>c[i], adj[a[i]].push_back(i), h[i]=-h[i], ans+=c[i];
    for(int i=1; i<=n; i++) if(!chk[i]) {
        int t=0;
        for(int j=i; ; chk[j]=true, j=a[i]) if(chk[j]) {
            t=j; break;
        }
        vector<int> v;
        for(int j=a[t]; j!=t; j=a[j]) v.push_back(j);
        v.push_back(t);
        map<int, int> res;
        for(int j=0; j<v.size(); j++) {
            map<int, int> tmp=dfs(v[j], v[(j+v.size()-1)%v.size()], v[j]);
            Merge(res, tmp);
        }
        int tmp=0, mx=0;
        for(auto j:res) tmp+=j.second, mx=max(mx, tmp);
        ans-=mx;
    }
    cout<<ans;
    return 0;
}

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