Submission #1239883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239883		Double_Slash	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	395 ms	105396 KiB

worst_reporter2

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

const int INF = 1e9;
int n, a[200001], h[200001], c[200001], sz;
struct Node {
    ll sum;
    int lc, rc;
} mem[1 << 23];
vector<int> adj[200001];
bool seen[200001];

void upd(int &n, int i, int v, int l, int r) {
    if (not n) n = ++sz;
    mem[n].sum += v;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (i <= m) upd(mem[n].lc, i, v, l, m);
    else upd(mem[n].rc, i, v, m + 1, r);
}

void erase(int &n, int i, int &v, int l, int r) {
    if (l > i or not v) return;
    if (r <= i and mem[n].sum <= v) {
        v -= mem[n].sum;
        n = 0;
    }
    if (not n) return;
    if (l == r) {
        mem[n].sum -= v;
        v = 0;
        return;
    }
    int m = (l + r) >> 1;
    erase(mem[n].rc, i, v, m + 1, r);
    erase(mem[n].lc, i, v, l, m);
    mem[n].sum = mem[mem[n].lc].sum + mem[mem[n].rc].sum;
}

ll query(int n, int i, int l, int r) {
    if (not n or r < i) return 0;
    if (l >= i) return mem[n].sum;
    int m = (l + r) >> 1;
    return query(mem[n].lc, i, l, m) + query(mem[n].rc, i, m + 1, r);
}

int merge(int a, int b) {
    if (not a or not b) return max(a, b);
    mem[a].sum += mem[b].sum;
    mem[a].lc = merge(mem[a].lc, mem[b].lc);
    mem[a].rc = merge(mem[a].rc, mem[b].rc);
    return a;
}

int dfs(int i) {
    seen[i] = true;
    int root = 0;
    for (int j: adj[i]) root = merge(root, dfs(j));
    upd(root, h[i], c[i], 1, INF);
    erase(root, h[i] - 1, c[i], 1, INF);
    return root;
}

int main() {
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> h[i] >> c[i];
        adj[a[i]].emplace_back(i);
        sum += c[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (seen[i]) continue;
        int j = i;
        for (int k = a[i]; j != k; k = a[a[k]]) j = a[j];
        vector<int> cycle{j};
        while (a[cycle.back()] != cycle[0]) cycle.emplace_back(a[cycle.back()]);
        for (int j: cycle) seen[j] = true;
        int root = 0;
        map<int, ll> m;
        for (int j: cycle) {
            for (int k: adj[j]) {
                if (not seen[k]) root = merge(root, dfs(k));
            }
            m[h[j]] += c[j];
        }
        ll mx = mem[root].sum;
        for (auto [k, v]: m) mx = max(mx, query(root, k, 1, INF) + v);
        sum -= mx;
    }
    cout << sum;
}

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