Submission #418192

#	Time	Username	Problem	Language	Result	Execution time	Memory
418192		lyc	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	478 ms	117704 KiB

worst_reporter2

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

const int mxN = 2e5+5;

int N, A[mxN], H[mxN], C[mxN], V;
vector<int> al[mxN], vals;

map<int,ll> dp[mxN];

void dfs(int u) {
    //FOR(x,0,V-1) dp[u][x] = 0;

    dp[u].insert(make_pair(0,0));
    for (int v : al[u]) {
        dfs(v);

        //FOR(x,0,V-1){
        //    ll cur = dp[v][x] + C[v];
        //    if (x <= H[v]) cur = min(cur, dp[v][H[v]]);
        //    dp[u][x] += cur;
        //}

        if (dp[v].count(H[v]+1)) dp[v][H[v]+1] += C[v];
        else dp[v].insert(make_pair(H[v]+1, C[v]));
        
        if (0 < H[v]) {
            if (dp[v].count(0)) dp[v][0] += C[v];
            else dp[v].insert(make_pair(0,C[v]));

            auto it = --dp[v].lower_bound(H[v]+1);
            while (it != dp[v].begin() && it->second <= C[v]) {
                auto x = prev(it);
                x->second += it->second;
                dp[v].erase(it);
                it = x;
            }
            it->second -= C[v];
        }

    //cout << u << " to " << v << ": ";
    //for (auto& x : dp[v]) {
    //    cout << vals[x.first] << " " << x.second << ", ";
    //}
    //cout << endl;

        if (SZ(dp[v]) > SZ(dp[u])) swap(dp[v],dp[u]);
        for (auto& x : dp[v]) {
            if (dp[u].count(x.first)) dp[u][x.first] += x.second;
            else dp[u].insert(x);
        }
    }

    //cout << u << ": ";
    //for (auto& x : dp[u]) {
    //    cout << x.first << " " << x.second << ", ";
    //}
    //cout << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> A[i] >> H[i] >> C[i];
        if (i != 1) al[A[i]].push_back(i);
        vals.push_back(H[i]);
    }

    vals.push_back(1);
    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());
    FOR(i,1,N){
        H[i] = lower_bound(ALL(vals),H[i])-vals.begin();
    }
    V = SZ(vals);

    dfs(1);

    //cout << min(dp[1][0] + C[1], dp[1][H[1]]) << '\n';
    ll ans = 1e18, cur = 0;
    for (auto& x : dp[1]) {
        if (x.first > 0) ans = min(ans, cur + C[1]);
        if (x.first > H[1]) ans = min(ans, cur);
        cur += x.second;
    }
    ans = min(ans, cur + C[1]);
    if (dp[1].rbegin()->first >= H[1]) ans = min(ans, cur);

    cout << ans << '\n';
}

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