Submission #1215706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215706		onbert	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	79 / 100	253 ms	55948 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 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]});
    // cout << u << endl;
    // for (auto [x, y]:s[U]) cout << x << " " << y << endl;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int all = 0;
    for (int i=1;i<=n;i++) {
        int p;
        cin >> p >> a[i] >> c[i];
        if (i != 1) adj[p].push_back(i);
        all += c[i];
    }
    for (int i=1;i<=n;i++) dsu[i] = i;
    dfs(1);
    vector<int> vec;
    for (auto [x, y]:s[rt(1)]) vec.push_back(y);
    reverse(vec.begin(), vec.end());
    int ans = 0, cur = 0;
    for (auto i:vec) {
        cur += i;
        ans = max(cur, ans);
    }
    cout << all - ans << "\n";
}

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