oj.uz

Submission #435658

# Submission time Handle Problem Language Result Execution time Memory
435658 2021-06-23T14:21:24 Z 2qbingxuan Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 2000 ms 8388 KB 
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (auto it = L; it != R; ++it)
        std::cerr << *it << ' ';
    std::cerr << "]\033[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
using ll = int64_t;
const int maxn = 100025, maxm = 10000;

int H[maxn], C[maxn];
vector<int> g[maxn];
map<int,ll> sub[maxn];
void insert(map<int,ll> &mp, int H, ll v) {
    auto it = mp.lower_bound(H);
    if (it != mp.end() && it -> second >= v) return;
    while (it != mp.begin() && prev(it)->second <= v)
        mp.erase(prev(it));
    mp[H] = v;
}
ll query(map<int,ll> &mp, int H) {
    auto it = mp.lower_bound(H);
    if (it == mp.end()) return 0;
    return it -> second;
}
void join(int a, int b) {
    map<int,ll> result;
    for (auto [h, val]: sub[a])
        insert(result, h, val + query(sub[b], h));
    for (auto [h, val]: sub[b])
        insert(result, h, val + query(sub[a], h));
    sub[b] = result;
    sub[a].clear();
}
void dfs(int i) {
    ll value = C[i];
    for (int j: g[i]) {
        dfs(j);
        value += query(sub[j], H[i]);
        join(j, i);
    }
    insert(sub[i], H[i], value);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    ll tot = 0;
    for (int i = 0; i < n; i++) {
        int A;
        cin >> A >> H[i] >> C[i];
        tot += C[i];
        --A;
        if (i) g[A].push_back(i);
    }
    dfs(0);
    ll best = 0;
    for (auto [h, val]: sub[0]) best = max(best, val);
    cout << tot - best << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7244 KB Output is correct
2 Correct 7 ms 7244 KB Output is correct
3 Correct 6 ms 7352 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 43 ms 8128 KB Output is correct
6 Correct 19 ms 7648 KB Output is correct
7 Correct 12 ms 7500 KB Output is correct
8 Correct 35 ms 8120 KB Output is correct
9 Correct 17 ms 7636 KB Output is correct
10 Correct 12 ms 7616 KB Output is correct
11 Correct 9 ms 7500 KB Output is correct
12 Correct 108 ms 8092 KB Output is correct
13 Correct 19 ms 8012 KB Output is correct
14 Correct 78 ms 7896 KB Output is correct
15 Correct 45 ms 7884 KB Output is correct
16 Correct 21 ms 8140 KB Output is correct
17 Correct 15 ms 7628 KB Output is correct
18 Correct 9 ms 7500 KB Output is correct
19 Correct 1315 ms 8388 KB Output is correct
20 Correct 77 ms 7796 KB Output is correct
21 Correct 12 ms 7756 KB Output is correct
22 Execution timed out 2067 ms 8132 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7244 KB Output is correct
2 Correct 7 ms 7244 KB Output is correct
3 Correct 6 ms 7352 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 43 ms 8128 KB Output is correct
6 Correct 19 ms 7648 KB Output is correct
7 Correct 12 ms 7500 KB Output is correct
8 Correct 35 ms 8120 KB Output is correct
9 Correct 17 ms 7636 KB Output is correct
10 Correct 12 ms 7616 KB Output is correct
11 Correct 9 ms 7500 KB Output is correct
12 Correct 108 ms 8092 KB Output is correct
13 Correct 19 ms 8012 KB Output is correct
14 Correct 78 ms 7896 KB Output is correct
15 Correct 45 ms 7884 KB Output is correct
16 Correct 21 ms 8140 KB Output is correct
17 Correct 15 ms 7628 KB Output is correct
18 Correct 9 ms 7500 KB Output is correct
19 Correct 1315 ms 8388 KB Output is correct
20 Correct 77 ms 7796 KB Output is correct
21 Correct 12 ms 7756 KB Output is correct
22 Execution timed out 2067 ms 8132 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7244 KB Output is correct
2 Correct 7 ms 7244 KB Output is correct
3 Correct 6 ms 7352 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 43 ms 8128 KB Output is correct
6 Correct 19 ms 7648 KB Output is correct
7 Correct 12 ms 7500 KB Output is correct
8 Correct 35 ms 8120 KB Output is correct
9 Correct 17 ms 7636 KB Output is correct
10 Correct 12 ms 7616 KB Output is correct
11 Correct 9 ms 7500 KB Output is correct
12 Correct 108 ms 8092 KB Output is correct
13 Correct 19 ms 8012 KB Output is correct
14 Correct 78 ms 7896 KB Output is correct
15 Correct 45 ms 7884 KB Output is correct
16 Correct 21 ms 8140 KB Output is correct
17 Correct 15 ms 7628 KB Output is correct
18 Correct 9 ms 7500 KB Output is correct
19 Correct 1315 ms 8388 KB Output is correct
20 Correct 77 ms 7796 KB Output is correct
21 Correct 12 ms 7756 KB Output is correct
22 Execution timed out 2067 ms 8132 KB Time limit exceeded
23 Halted 0 ms 0 KB -