oj.uz

Submission #418187

# Submission time Handle Problem Language Result Execution time Memory
418187 2021-06-05T07:51:33 Z lyc Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 1 ms 676 KB 
#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;
const int mxN = 5e3+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]) {
        cur += x.second;
        if (x.first <= 0) ans = min(ans, cur + C[1]);
        if (x.first >= H[1]) ans = min(ans, cur);
    }
    cout << ans << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 676 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Incorrect 1 ms 588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 676 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Incorrect 1 ms 588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 676 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Incorrect 1 ms 588 KB Output isn't correct
5 Halted 0 ms 0 KB -