Submission #973969

#	Time	Username	Problem	Language	Result	Execution time	Memory
973969		phoenix	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	345 ms	195644 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200200;

int n;

int p[N];
int h[N];
int c[N];

map<int, ll> mp[N];
vector<int> g[N];

// u <- v
void join(int u, int v) {
    if ((int)mp[u].size() < (int)mp[v].size()) swap(mp[u], mp[v]);
    for (auto c : mp[v]) 
        mp[u][c.first] += c.second; 
};

bool vis[N];

void dfs(int v) {
    vis[v] = true;
    for (int to : g[v]) {
        dfs(to);
        join(v, to);
    }
    int s = c[v];
    auto it = mp[v].upper_bound(h[v]);
    while (it != mp[v].begin()) {
        it--;
        if (s >= it->second) {
            s -= it->second;
            mp[v].erase(it);
        } else {
            mp[v][it->first] = it->second - s;
            s = 0;
            break;
        }
        it = mp[v].upper_bound(h[v]);
    }
    mp[v][0] += c[v] - s;
    mp[v][h[v] + 1] += c[v];    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> p[i] >> h[i] >> c[i];

    vector<deque<int>> cycles;

    for (int i = 1; i <= n; i++) if (!vis[i]) {
        deque<int> cyc;
        int x = i;
        while (!vis[x]) {
            vis[x] = true;
            cyc.push_back(x);
            x = p[x];
        }
        while (!cyc.empty() && cyc.front() != x) cyc.pop_front();
        // cout << '{';
        // for (int c : cyc) cout << c << ' ';
        // cout << '}' << '\n';
        if (!cyc.empty()) 
            cycles.push_back(cyc);
    }    
    for (int i = 1; i <= n; i++) vis[i] = false;

    for (auto c : cycles) for (int x : c) 
        vis[x] = true;
    for (int i = 1; i <= n; i++) if (!vis[i]) 
        g[p[i]].push_back(i);

    ll res = 0;
    for (auto cyc : cycles) {
        for (int v : cyc) {
            for (int to : g[v]) {
                dfs(to);   
                join(v, to);
            }
            mp[v][0] += c[v];
            mp[v][h[v]] -= c[v];
            mp[v][h[v] + 1] += c[v];
        }
        for (int v : cyc)
            if (v != cyc.back()) 
                join(cyc.back(), v);
        ll val = 0;
        ll mn = 1e18;
        for (auto c : mp[cyc.back()]) {
            val += c.second;
            if (val < mn) mn = val;
        }   
        res += mn;
    }
    cout << res;
    return 0;
}

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