Submission #1229233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229233		__moin__	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	496 ms	589824 KiB

worst_reporter2

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

#define int long long

__int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    vector<int> par(n);
    vector<vector<int>> children(n);
    vector<int> value(n);
    vector<int> cost(n);

    set<int> values;

    for (int i = 0; i < n; i++) {
        cin >> par[i] >> value[i] >> cost[i];
        par[i]--;
        if (par[i] != i) children[par[i]].push_back(i);
        values.insert(value[i]);
    }

    vector<int> dist_values;
    for (int e : values) dist_values.push_back(e);

    vector<vector<int>> dp(n, vector<int>(dist_values.size()));
    vector<vector<int>> dpleq(n, vector<int>(dist_values.size()));

    function<void(int)> dfs = [&](int v) {
        for (int c : children[v]) {
            dfs(c);
        }
        for (int val = 0; val < dist_values.size(); val++) {
            dp[v][val] = dist_values[val] == value[v] ? 0 : cost[v];
            for (int c : children[v]) dp[v][val] += dpleq[c][val];
        }
        dpleq[v] = dp[v];
        for (int val = dist_values.size() - 2; val >= 0; val--) dpleq[v][val] = min(dpleq[v][val], dpleq[v][val+1]);
    };

    dfs(0);

    cout << dpleq[0][0] << "\n";

    return 0;
}

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