Submission #1215906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215906		onbert	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	261 ms	61544 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, INF = 1e10;
int n;
vector<int> adj[maxn];
int p[maxn], a[maxn], c[maxn];

int dsu[maxn];
multiset<pair<int,int>> s[maxn];

int rt(int u) {
    if (dsu[u] == u) return u;
    return dsu[u] = rt(dsu[u]);
}
void merge(int u, int v) {
    u = rt(u), v = rt(v);
    if (s[u].size() > s[v].size()) swap(u, v);
    dsu[u] = v;
    for (auto [x, y]:s[u]) s[v].insert({x, y});
    while (s[u].size()) s[u].erase(s[u].begin());
}

void dfs(int u) {
    for (int v:adj[u]) {
        dfs(v);
        merge(u, v);
    }
    int U = rt(u);
    int val = -c[u];
    while (s[U].size() && s[U].begin()->first < a[u]) {
        pair<int,int> cur = *prev(s[U].lower_bound({a[u], -INF}));
        s[U].erase(s[U].find(cur));
        val += cur.second;
        if (val > 0) {
            s[U].insert({cur.first, val});
            break;
        }
    }
    s[U].insert({a[u], c[u]});
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int all = 0;
    for (int i=1;i<=n;i++) {
        cin >> p[i] >> a[i] >> c[i];
        adj[p[i]].push_back(i);
        all += c[i];
    }


    for (int i=1;i<=n;i++) dsu[i] = i;

    int vis[maxn];
    bool inloop[maxn];
    for (int i=1;i<=n;i++) vis[i] = inloop[i] = 0;
    int ans = 0;
    for (int i=1;i<=n;i++) if (!vis[i]) {
        vector<int> track;
        int u = i;
        int last = -1;
        // cout << i << endl;
        while (true) {
            // cout << u << " ";
            vis[u] = 1, track.push_back(u);
            int v = p[u];
            if (vis[v] == 1) {
                last = v;
                break;
            } else if (vis[v] == 2) break;
            u = v;
        }
        // cout << endl;
        for (int j:track) vis[j] = 2;
        if (last == -1) continue;

        for (int j=(int)track.size()-1;j>=0;j--) {
            inloop[track[j]] = true;
            if (track[j] == last) break;
        }

        // cout << i << endl;

        map<int,int> mp;
        while (track.size()) {
            u = track.back();
            mp[a[u]] += c[u];
            // cout << u << endl;
            for (int v:adj[u]) if (!inloop[v]) {
                // cout << "test " << v << endl;
                dfs(v);
                merge(last, v);
            }
            if (u == last) break;
            track.pop_back();
        }
        vector<pair<int,int>> loop = {{0, 0}};
        for (auto [x, y]:mp) loop.push_back({x, y});
        vector<pair<int,int>> vec;
        for (auto [x, y]:s[rt(last)]) vec.push_back({x, y});
        reverse(vec.begin(), vec.end());
        int pt = loop.size();
        int cur = 0, curmx = 0, curans = 0;
        for (auto [x, y]:vec) {
            while (pt-1 >= 0 && loop[pt-1].first > x) {
                pt--;
                curans = max(curmx + loop[pt].second, curans);
            }
            cur += y;
            curmx = max(curmx, cur);
        }
        while (pt-1 >= 0) {
            pt--;
            curans = max(curmx + loop[pt].second, curans);
        }
        ans += curans;
        // cout << i << endl;
        // cout << ans << endl;
    }
    cout << all - ans << "\n";
}

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