oj.uz

Submission #674933

# Submission time Handle Problem Language Result Execution time Memory
674933 2022-12-26T16:04:46 Z skittles1412 Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 134 ms 201812 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5056 KB Output is correct
3 Correct 3 ms 5064 KB Output is correct
4 Correct 5 ms 5060 KB Output is correct
5 Correct 47 ms 6112 KB Output is correct
6 Correct 37 ms 6128 KB Output is correct
7 Correct 36 ms 6100 KB Output is correct
8 Correct 47 ms 5964 KB Output is correct
9 Correct 43 ms 6000 KB Output is correct
10 Correct 36 ms 5976 KB Output is correct
11 Correct 35 ms 6000 KB Output is correct
12 Correct 133 ms 201772 KB Output is correct
13 Correct 119 ms 201800 KB Output is correct
14 Correct 101 ms 103644 KB Output is correct
15 Correct 100 ms 103644 KB Output is correct
16 Correct 47 ms 5844 KB Output is correct
17 Correct 35 ms 5844 KB Output is correct
18 Correct 35 ms 5840 KB Output is correct
19 Correct 88 ms 103496 KB Output is correct
20 Correct 77 ms 103564 KB Output is correct
21 Correct 83 ms 103608 KB Output is correct
22 Correct 48 ms 5352 KB Output is correct
23 Correct 34 ms 5344 KB Output is correct
24 Correct 91 ms 103528 KB Output is correct
25 Correct 77 ms 103584 KB Output is correct
26 Correct 134 ms 201812 KB Output is correct
27 Correct 94 ms 83968 KB Output is correct
28 Correct 101 ms 123144 KB Output is correct
29 Correct 114 ms 162496 KB Output is correct
30 Correct 103 ms 103624 KB Output is correct
31 Correct 123 ms 103472 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5056 KB Output is correct
3 Correct 3 ms 5064 KB Output is correct
4 Correct 5 ms 5060 KB Output is correct
5 Correct 47 ms 6112 KB Output is correct
6 Correct 37 ms 6128 KB Output is correct
7 Correct 36 ms 6100 KB Output is correct
8 Correct 47 ms 5964 KB Output is correct
9 Correct 43 ms 6000 KB Output is correct
10 Correct 36 ms 5976 KB Output is correct
11 Correct 35 ms 6000 KB Output is correct
12 Correct 133 ms 201772 KB Output is correct
13 Correct 119 ms 201800 KB Output is correct
14 Correct 101 ms 103644 KB Output is correct
15 Correct 100 ms 103644 KB Output is correct
16 Correct 47 ms 5844 KB Output is correct
17 Correct 35 ms 5844 KB Output is correct
18 Correct 35 ms 5840 KB Output is correct
19 Correct 88 ms 103496 KB Output is correct
20 Correct 77 ms 103564 KB Output is correct
21 Correct 83 ms 103608 KB Output is correct
22 Correct 48 ms 5352 KB Output is correct
23 Correct 34 ms 5344 KB Output is correct
24 Correct 91 ms 103528 KB Output is correct
25 Correct 77 ms 103584 KB Output is correct
26 Correct 134 ms 201812 KB Output is correct
27 Correct 94 ms 83968 KB Output is correct
28 Correct 101 ms 123144 KB Output is correct
29 Correct 114 ms 162496 KB Output is correct
30 Correct 103 ms 103624 KB Output is correct
31 Correct 123 ms 103472 KB Output is correct
32 Correct 49 ms 6108 KB Output is correct
33 Runtime error 120 ms 29064 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5056 KB Output is correct
3 Correct 3 ms 5064 KB Output is correct
4 Correct 5 ms 5060 KB Output is correct
5 Correct 47 ms 6112 KB Output is correct
6 Correct 37 ms 6128 KB Output is correct
7 Correct 36 ms 6100 KB Output is correct
8 Correct 47 ms 5964 KB Output is correct
9 Correct 43 ms 6000 KB Output is correct
10 Correct 36 ms 5976 KB Output is correct
11 Correct 35 ms 6000 KB Output is correct
12 Correct 133 ms 201772 KB Output is correct
13 Correct 119 ms 201800 KB Output is correct
14 Correct 101 ms 103644 KB Output is correct
15 Correct 100 ms 103644 KB Output is correct
16 Correct 47 ms 5844 KB Output is correct
17 Correct 35 ms 5844 KB Output is correct
18 Correct 35 ms 5840 KB Output is correct
19 Correct 88 ms 103496 KB Output is correct
20 Correct 77 ms 103564 KB Output is correct
21 Correct 83 ms 103608 KB Output is correct
22 Correct 48 ms 5352 KB Output is correct
23 Correct 34 ms 5344 KB Output is correct
24 Correct 91 ms 103528 KB Output is correct
25 Correct 77 ms 103584 KB Output is correct
26 Correct 134 ms 201812 KB Output is correct
27 Correct 94 ms 83968 KB Output is correct
28 Correct 101 ms 123144 KB Output is correct
29 Correct 114 ms 162496 KB Output is correct
30 Correct 103 ms 103624 KB Output is correct
31 Correct 123 ms 103472 KB Output is correct
32 Correct 49 ms 6108 KB Output is correct
33 Runtime error 120 ms 29064 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -