oj.uz

답안 #914491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914491 2024-01-22T09:10:53 Z Tuanlinh123 Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 303 ms 105228 KB 
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
ll H[maxn], C[maxn];
map <ll, ll> cnt[maxn];
vector <ll> A[maxn];

void dfs(ll u)
{
    for (ll v:A[u])
    {
        dfs(v);
        if (cnt[u].size()<cnt[v].size())
            swap(cnt[u], cnt[v]);
        for (pll i:cnt[v])
            cnt[u][i.fi]+=i.se;
    }
    ll crr=C[u]; cnt[u][H[u]]+=crr;
    auto it=cnt[u].lower_bound(H[u]);
    while (it!=cnt[u].begin())
    {
        it--;
        if ((*it).se>crr) {(*it).se-=crr;break;}
        crr-=(*it).se; it=cnt[u].erase(it);
    }
    // cout << u << "\n";
    // for (pll i:cnt[u]) cout << i.fi << " " << i.se << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, sum=0; cin >> n;
    for (ll i=1; i<=n; i++)
    {
        ll a; cin >> a;
        if (i!=1) A[a].pb(i);
        cin >> H[i] >> C[i]; sum+=C[i];
    }
    dfs(1);
    for (pll i:cnt[1]) sum-=i.se;
    cout << sum << "\n";
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 9 ms 18012 KB Output is correct
6 Correct 8 ms 17756 KB Output is correct
7 Correct 7 ms 17500 KB Output is correct
8 Correct 9 ms 18268 KB Output is correct
9 Correct 8 ms 17756 KB Output is correct
10 Correct 7 ms 17340 KB Output is correct
11 Correct 7 ms 17240 KB Output is correct
12 Correct 7 ms 18008 KB Output is correct
13 Correct 6 ms 17944 KB Output is correct
14 Correct 7 ms 17524 KB Output is correct
15 Correct 7 ms 17592 KB Output is correct
16 Correct 9 ms 18776 KB Output is correct
17 Correct 9 ms 17820 KB Output is correct
18 Correct 6 ms 17244 KB Output is correct
19 Correct 7 ms 17752 KB Output is correct
20 Correct 7 ms 17756 KB Output is correct
21 Correct 6 ms 17588 KB Output is correct
22 Correct 7 ms 17688 KB Output is correct
23 Correct 6 ms 17496 KB Output is correct
24 Correct 7 ms 17752 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 18008 KB Output is correct
27 Correct 8 ms 17756 KB Output is correct
28 Correct 7 ms 18012 KB Output is correct
29 Correct 7 ms 18012 KB Output is correct
30 Correct 7 ms 18072 KB Output is correct
31 Correct 8 ms 18012 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 9 ms 18012 KB Output is correct
6 Correct 8 ms 17756 KB Output is correct
7 Correct 7 ms 17500 KB Output is correct
8 Correct 9 ms 18268 KB Output is correct
9 Correct 8 ms 17756 KB Output is correct
10 Correct 7 ms 17340 KB Output is correct
11 Correct 7 ms 17240 KB Output is correct
12 Correct 7 ms 18008 KB Output is correct
13 Correct 6 ms 17944 KB Output is correct
14 Correct 7 ms 17524 KB Output is correct
15 Correct 7 ms 17592 KB Output is correct
16 Correct 9 ms 18776 KB Output is correct
17 Correct 9 ms 17820 KB Output is correct
18 Correct 6 ms 17244 KB Output is correct
19 Correct 7 ms 17752 KB Output is correct
20 Correct 7 ms 17756 KB Output is correct
21 Correct 6 ms 17588 KB Output is correct
22 Correct 7 ms 17688 KB Output is correct
23 Correct 6 ms 17496 KB Output is correct
24 Correct 7 ms 17752 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 18008 KB Output is correct
27 Correct 8 ms 17756 KB Output is correct
28 Correct 7 ms 18012 KB Output is correct
29 Correct 7 ms 18012 KB Output is correct
30 Correct 7 ms 18072 KB Output is correct
31 Correct 8 ms 18012 KB Output is correct
32 Correct 9 ms 18012 KB Output is correct
33 Correct 303 ms 80844 KB Output is correct
34 Correct 219 ms 55892 KB Output is correct
35 Correct 287 ms 77656 KB Output is correct
36 Correct 253 ms 56296 KB Output is correct
37 Correct 140 ms 36944 KB Output is correct
38 Correct 116 ms 32328 KB Output is correct
39 Correct 114 ms 57288 KB Output is correct
40 Correct 104 ms 57168 KB Output is correct
41 Correct 80 ms 57244 KB Output is correct
42 Correct 105 ms 43088 KB Output is correct
43 Correct 98 ms 42968 KB Output is correct
44 Correct 271 ms 105228 KB Output is correct
45 Correct 195 ms 69676 KB Output is correct
46 Correct 66 ms 31872 KB Output is correct
47 Correct 192 ms 53076 KB Output is correct
48 Correct 94 ms 46164 KB Output is correct
49 Correct 73 ms 46128 KB Output is correct
50 Correct 221 ms 48328 KB Output is correct
51 Correct 72 ms 36040 KB Output is correct
52 Correct 190 ms 54124 KB Output is correct
53 Correct 86 ms 46980 KB Output is correct
54 Correct 83 ms 57424 KB Output is correct
55 Correct 158 ms 55376 KB Output is correct
56 Correct 136 ms 60796 KB Output is correct
57 Correct 140 ms 63612 KB Output is correct
58 Correct 138 ms 61196 KB Output is correct
59 Correct 135 ms 61088 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 9 ms 18012 KB Output is correct
6 Correct 8 ms 17756 KB Output is correct
7 Correct 7 ms 17500 KB Output is correct
8 Correct 9 ms 18268 KB Output is correct
9 Correct 8 ms 17756 KB Output is correct
10 Correct 7 ms 17340 KB Output is correct
11 Correct 7 ms 17240 KB Output is correct
12 Correct 7 ms 18008 KB Output is correct
13 Correct 6 ms 17944 KB Output is correct
14 Correct 7 ms 17524 KB Output is correct
15 Correct 7 ms 17592 KB Output is correct
16 Correct 9 ms 18776 KB Output is correct
17 Correct 9 ms 17820 KB Output is correct
18 Correct 6 ms 17244 KB Output is correct
19 Correct 7 ms 17752 KB Output is correct
20 Correct 7 ms 17756 KB Output is correct
21 Correct 6 ms 17588 KB Output is correct
22 Correct 7 ms 17688 KB Output is correct
23 Correct 6 ms 17496 KB Output is correct
24 Correct 7 ms 17752 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 18008 KB Output is correct
27 Correct 8 ms 17756 KB Output is correct
28 Correct 7 ms 18012 KB Output is correct
29 Correct 7 ms 18012 KB Output is correct
30 Correct 7 ms 18072 KB Output is correct
31 Correct 8 ms 18012 KB Output is correct
32 Correct 9 ms 18012 KB Output is correct
33 Correct 303 ms 80844 KB Output is correct
34 Correct 219 ms 55892 KB Output is correct
35 Correct 287 ms 77656 KB Output is correct
36 Correct 253 ms 56296 KB Output is correct
37 Correct 140 ms 36944 KB Output is correct
38 Correct 116 ms 32328 KB Output is correct
39 Correct 114 ms 57288 KB Output is correct
40 Correct 104 ms 57168 KB Output is correct
41 Correct 80 ms 57244 KB Output is correct
42 Correct 105 ms 43088 KB Output is correct
43 Correct 98 ms 42968 KB Output is correct
44 Correct 271 ms 105228 KB Output is correct
45 Correct 195 ms 69676 KB Output is correct
46 Correct 66 ms 31872 KB Output is correct
47 Correct 192 ms 53076 KB Output is correct
48 Correct 94 ms 46164 KB Output is correct
49 Correct 73 ms 46128 KB Output is correct
50 Correct 221 ms 48328 KB Output is correct
51 Correct 72 ms 36040 KB Output is correct
52 Correct 190 ms 54124 KB Output is correct
53 Correct 86 ms 46980 KB Output is correct
54 Correct 83 ms 57424 KB Output is correct
55 Correct 158 ms 55376 KB Output is correct
56 Correct 136 ms 60796 KB Output is correct
57 Correct 140 ms 63612 KB Output is correct
58 Correct 138 ms 61196 KB Output is correct
59 Correct 135 ms 61088 KB Output is correct
60 Correct 4 ms 16984 KB Output is correct
61 Incorrect 4 ms 16988 KB Output isn't correct
62 Halted 0 ms 0 KB -