oj.uz

Submission #518945

# Submission time Handle Problem Language Result Execution time Memory
518945 2022-01-25T08:59:12 Z ParsaAlizadeh Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 537 ms 35908 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second
#define lc (id<<1)
#define rc (lc|1)

void assume(int expr) {
    if (!expr) __builtin_unreachable();
}

constexpr int N = 2e5 + 10;

int n, L[N], R[N];
ll H[N], C[N], dp[N];
vector<int> adj[N];

namespace Seg {
    ll seg[N<<2];
    void modify(int id, int l, int r, int ind, ll c) {
        if (r-l == 1) {
            seg[id] = c;
            return;
        }
        int mid = (l+r) >> 1;
        if (ind < mid) modify(lc, l, mid, ind, c);
        else modify(rc, mid, r, ind, c);
        seg[id] = seg[lc] + seg[rc];
    }
    ll get(int id, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql)
            return 0;
        if (ql <= l && r <= qr)
            return seg[id];
        int mid = (l+r) >> 1;
        return get(lc, l, mid, ql, qr) + get(rc, mid, r, ql, qr);
    }
}

namespace JadSeg {
    int seg[N<<2];
    void build(int id, int l, int r) {
        if (r-l == 1) {
            seg[id] = l;
            return;
        }
        int mid = (l+r) >> 1;
        build(lc, l, mid); build(rc, mid, r);
        seg[id] = max(seg[lc], seg[rc]);
    }
    void modify(int id, int l, int r, int ind, int c) {
        if (r-l == 1) {
            seg[id] = c;
            return;
        }
        int mid = (l+r) >> 1;
        if (ind < mid)
            modify(lc, l, mid, ind, c);
        else
            modify(rc, mid, r, ind, c);
        seg[id] = max(seg[lc], seg[rc]);
    }
    int get(int id, int l, int r, int ind) {
        if (l >= ind || seg[id] <= ind)
            return -1;
        if (r-l == 1)
            return l;
        int mid = (l+r) >> 1;
        auto res = get(rc, mid, r, ind);
        if (res != -1)
            return res;
        return get(lc, l, mid, ind);
    }
}

void dfs(int u) {
    static int timer = 0;
    L[u] = timer++;
    for (int v : adj[u])
        dfs(v);
    R[u] = timer;
}

void ignre(int i, ll c) {
    // cout << "ignore " << i << ' ' <<c << endl;
    int jad = JadSeg::get(1, 0, n, i);
    if (jad == -1)
        return;
    ll val = Seg::get(1, 0, n, jad, jad+1);
    // cout << "@ " << jad << ' ' << val << endl;
    val -= c;
    if (val >= 0) {
        Seg::modify(1, 0, n, jad, val);
        return;
    }
    Seg::modify(1, 0, n, jad, 0);
    JadSeg::modify(1, 0, n, jad, jad);
    return ignre(jad, -val);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int par;
        cin >> par >> H[i] >> C[i];
        if (i > 1)
            adj[par].push_back(i);
    }
    dfs(1);
    vector<pair<ll,int>> Q;
    Q.reserve(n);
    for (int i = 1; i <= n; i++) {
        Q.emplace_back(H[i], i);
    }
    sort(all(Q), greater<>());
    for (int qi = 0; qi < Q.size(); qi++) {
        int i = Q[qi].snd;
        dp[i] = Seg::get(1, 0, n, L[i], R[i]) + C[i];
        // cout << "add " << L[i] << ' ' << C[i] << endl;
        Seg::modify(1, 0, n, L[i], C[i]);
        JadSeg::modify(1, 0, n, L[i], R[i]);
        ignre(L[i], C[i]);
    }
    ll sm = 0, ans = Seg::get(1, 0, n, 0, n);
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
        sm += C[i];
    }
    // cout << sm << ' ' << ans << endl;
    cout << sm - ans << '\n';
    return 0;
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:123:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int qi = 0; qi < Q.size(); qi++) {
      |                      ~~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 9 ms 5552 KB Output is correct
7 Correct 8 ms 5676 KB Output is correct
8 Correct 11 ms 5680 KB Output is correct
9 Correct 9 ms 5696 KB Output is correct
10 Correct 9 ms 5588 KB Output is correct
11 Correct 7 ms 5584 KB Output is correct
12 Correct 11 ms 5816 KB Output is correct
13 Correct 14 ms 5848 KB Output is correct
14 Correct 13 ms 5820 KB Output is correct
15 Correct 10 ms 5700 KB Output is correct
16 Correct 10 ms 5676 KB Output is correct
17 Correct 12 ms 5680 KB Output is correct
18 Correct 7 ms 5580 KB Output is correct
19 Correct 10 ms 5708 KB Output is correct
20 Correct 11 ms 5604 KB Output is correct
21 Correct 9 ms 5672 KB Output is correct
22 Correct 7 ms 5560 KB Output is correct
23 Correct 7 ms 5592 KB Output is correct
24 Correct 9 ms 5712 KB Output is correct
25 Correct 11 ms 5708 KB Output is correct
26 Correct 9 ms 5788 KB Output is correct
27 Correct 9 ms 5704 KB Output is correct
28 Correct 9 ms 5700 KB Output is correct
29 Correct 9 ms 5812 KB Output is correct
30 Correct 11 ms 5708 KB Output is correct
31 Correct 14 ms 5664 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 9 ms 5552 KB Output is correct
7 Correct 8 ms 5676 KB Output is correct
8 Correct 11 ms 5680 KB Output is correct
9 Correct 9 ms 5696 KB Output is correct
10 Correct 9 ms 5588 KB Output is correct
11 Correct 7 ms 5584 KB Output is correct
12 Correct 11 ms 5816 KB Output is correct
13 Correct 14 ms 5848 KB Output is correct
14 Correct 13 ms 5820 KB Output is correct
15 Correct 10 ms 5700 KB Output is correct
16 Correct 10 ms 5676 KB Output is correct
17 Correct 12 ms 5680 KB Output is correct
18 Correct 7 ms 5580 KB Output is correct
19 Correct 10 ms 5708 KB Output is correct
20 Correct 11 ms 5604 KB Output is correct
21 Correct 9 ms 5672 KB Output is correct
22 Correct 7 ms 5560 KB Output is correct
23 Correct 7 ms 5592 KB Output is correct
24 Correct 9 ms 5712 KB Output is correct
25 Correct 11 ms 5708 KB Output is correct
26 Correct 9 ms 5788 KB Output is correct
27 Correct 9 ms 5704 KB Output is correct
28 Correct 9 ms 5700 KB Output is correct
29 Correct 9 ms 5812 KB Output is correct
30 Correct 11 ms 5708 KB Output is correct
31 Correct 14 ms 5664 KB Output is correct
32 Correct 8 ms 5684 KB Output is correct
33 Correct 347 ms 26820 KB Output is correct
34 Correct 390 ms 26848 KB Output is correct
35 Correct 364 ms 26796 KB Output is correct
36 Correct 403 ms 26876 KB Output is correct
37 Correct 387 ms 26784 KB Output is correct
38 Correct 330 ms 26892 KB Output is correct
39 Correct 537 ms 35420 KB Output is correct
40 Correct 517 ms 35476 KB Output is correct
41 Correct 321 ms 35908 KB Output is correct
42 Correct 517 ms 33520 KB Output is correct
43 Correct 493 ms 33604 KB Output is correct
44 Correct 375 ms 27704 KB Output is correct
45 Correct 367 ms 27772 KB Output is correct
46 Correct 189 ms 27816 KB Output is correct
47 Correct 442 ms 30308 KB Output is correct
48 Correct 411 ms 30288 KB Output is correct
49 Correct 284 ms 30328 KB Output is correct
50 Correct 266 ms 25464 KB Output is correct
51 Correct 303 ms 25476 KB Output is correct
52 Correct 425 ms 30956 KB Output is correct
53 Correct 416 ms 30708 KB Output is correct
54 Correct 204 ms 35708 KB Output is correct
55 Correct 346 ms 30124 KB Output is correct
56 Correct 345 ms 32688 KB Output is correct
57 Correct 353 ms 33840 KB Output is correct
58 Correct 385 ms 32968 KB Output is correct
59 Correct 404 ms 32964 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 9 ms 5552 KB Output is correct
7 Correct 8 ms 5676 KB Output is correct
8 Correct 11 ms 5680 KB Output is correct
9 Correct 9 ms 5696 KB Output is correct
10 Correct 9 ms 5588 KB Output is correct
11 Correct 7 ms 5584 KB Output is correct
12 Correct 11 ms 5816 KB Output is correct
13 Correct 14 ms 5848 KB Output is correct
14 Correct 13 ms 5820 KB Output is correct
15 Correct 10 ms 5700 KB Output is correct
16 Correct 10 ms 5676 KB Output is correct
17 Correct 12 ms 5680 KB Output is correct
18 Correct 7 ms 5580 KB Output is correct
19 Correct 10 ms 5708 KB Output is correct
20 Correct 11 ms 5604 KB Output is correct
21 Correct 9 ms 5672 KB Output is correct
22 Correct 7 ms 5560 KB Output is correct
23 Correct 7 ms 5592 KB Output is correct
24 Correct 9 ms 5712 KB Output is correct
25 Correct 11 ms 5708 KB Output is correct
26 Correct 9 ms 5788 KB Output is correct
27 Correct 9 ms 5704 KB Output is correct
28 Correct 9 ms 5700 KB Output is correct
29 Correct 9 ms 5812 KB Output is correct
30 Correct 11 ms 5708 KB Output is correct
31 Correct 14 ms 5664 KB Output is correct
32 Correct 8 ms 5684 KB Output is correct
33 Correct 347 ms 26820 KB Output is correct
34 Correct 390 ms 26848 KB Output is correct
35 Correct 364 ms 26796 KB Output is correct
36 Correct 403 ms 26876 KB Output is correct
37 Correct 387 ms 26784 KB Output is correct
38 Correct 330 ms 26892 KB Output is correct
39 Correct 537 ms 35420 KB Output is correct
40 Correct 517 ms 35476 KB Output is correct
41 Correct 321 ms 35908 KB Output is correct
42 Correct 517 ms 33520 KB Output is correct
43 Correct 493 ms 33604 KB Output is correct
44 Correct 375 ms 27704 KB Output is correct
45 Correct 367 ms 27772 KB Output is correct
46 Correct 189 ms 27816 KB Output is correct
47 Correct 442 ms 30308 KB Output is correct
48 Correct 411 ms 30288 KB Output is correct
49 Correct 284 ms 30328 KB Output is correct
50 Correct 266 ms 25464 KB Output is correct
51 Correct 303 ms 25476 KB Output is correct
52 Correct 425 ms 30956 KB Output is correct
53 Correct 416 ms 30708 KB Output is correct
54 Correct 204 ms 35708 KB Output is correct
55 Correct 346 ms 30124 KB Output is correct
56 Correct 345 ms 32688 KB Output is correct
57 Correct 353 ms 33840 KB Output is correct
58 Correct 385 ms 32968 KB Output is correct
59 Correct 404 ms 32964 KB Output is correct
60 Correct 4 ms 4940 KB Output is correct
61 Incorrect 3 ms 4940 KB Output isn't correct
62 Halted 0 ms 0 KB -