Submission #674933

#	Time	Username	Problem	Language	Result	Execution time	Memory
674933		skittles1412	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	134 ms	201812 KiB

worst_reporter2

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct DS {
    static constexpr int maxn = 5005;

    array<long, maxn> v {};

    friend void merge(DS& a, DS& b) {
        for (int i = 0; i < maxn; i++) {
            a.v[i] += b.v[i];
        }
    }

    long get(int i) const {
        return v[i];
    }

    void upd_add(long x) {
        for (auto& a : v) {
            a += x;
        }
    }

    void upd_min(int r, long x) {
        for (int i = 0; i <= r; i++) {
            assert(v[i] <= v[i + 1]);
            v[i] = min(v[i], x);
        }
    }
};

constexpr int maxn = 2e5 + 5;

int arr[maxn], cost[maxn];
vector<int> graph[maxn];

DS dp(int u, int p = -1) {
    DS cur;
    long cans = 0;
    for (auto& v : graph[u]) {
        if (v == p) {
            continue;
        }
        auto&& ndp = dp(v, u);
        cans += ndp.get(arr[u]);
        merge(cur, ndp);
    }
    cur.upd_add(cost[u]);
    cur.upd_min(arr[u], cans);
    return cur;
}

void solve() {
    int n;
    cin >> n;
    int par[n];
    for (int i = 0; i < n; i++) {
        cin >> par[i] >> arr[i] >> cost[i];
        par[i]--;
    }
    for (int i = 1; i < n; i++) {
        graph[par[i]].push_back(i);
    }
    vector<int> comp(arr, arr + n);
    sort(begin(comp), end(comp));
    comp.erase(unique(begin(comp), end(comp)), comp.end());
    for (int i = 0; i < n; i++) {
        arr[i] =
            int(lower_bound(begin(comp), end(comp), arr[i]) - comp.begin());
    }
    cout << dp(0).get(0) << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

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