oj.uz

Submission #1107668

# Submission time Handle Problem Language Result Execution time Memory
1107668 2024-11-01T21:58:13 Z imarn Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 268 ms 104520 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e5+5;
vector<int> g[mxn];
int a[mxn],h[mxn],c[mxn];
map<int,ll>dp[mxn];
bool vis[mxn]{0};
void dfs(int u){
    vis[u]=1;
    for(auto v:g[u]){
        if(vis[v])continue;
        dfs(v);
        if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]);
        for(auto it:dp[v])dp[u][it.f]+=it.s;
    }dp[u][h[u]]+=c[u];
    auto it = dp[u].upper_bound(h[u]);
    int cur=c[u];
    for(;it!=dp[u].end();){
        if(cur>=it->s){cur-=it->s;auto ij=it;it++;dp[u].erase(ij);}
        else {it->s-=cur;break;}
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;ll rs=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>h[i]>>c[i];h[i]=-h[i];
        g[a[i]].pb(i);rs+=c[i];
    }dfs(1);ll rs2=0;
    for(auto it:dp[1])rs2+=it.s;
    cout<<rs-rs2;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 6 ms 18000 KB Output is correct
6 Correct 6 ms 17488 KB Output is correct
7 Correct 6 ms 17304 KB Output is correct
8 Correct 7 ms 18000 KB Output is correct
9 Correct 5 ms 17488 KB Output is correct
10 Correct 6 ms 17232 KB Output is correct
11 Correct 4 ms 17232 KB Output is correct
12 Correct 5 ms 17704 KB Output is correct
13 Correct 5 ms 17744 KB Output is correct
14 Correct 5 ms 17488 KB Output is correct
15 Correct 5 ms 17656 KB Output is correct
16 Correct 7 ms 18256 KB Output is correct
17 Correct 6 ms 17744 KB Output is correct
18 Correct 4 ms 17156 KB Output is correct
19 Correct 5 ms 17912 KB Output is correct
20 Correct 5 ms 17488 KB Output is correct
21 Correct 4 ms 17488 KB Output is correct
22 Correct 5 ms 17488 KB Output is correct
23 Correct 5 ms 17400 KB Output is correct
24 Correct 5 ms 17744 KB Output is correct
25 Correct 5 ms 17488 KB Output is correct
26 Correct 5 ms 17744 KB Output is correct
27 Correct 6 ms 17744 KB Output is correct
28 Correct 5 ms 17744 KB Output is correct
29 Correct 5 ms 18000 KB Output is correct
30 Correct 5 ms 17968 KB Output is correct
31 Correct 5 ms 18000 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 6 ms 18000 KB Output is correct
6 Correct 6 ms 17488 KB Output is correct
7 Correct 6 ms 17304 KB Output is correct
8 Correct 7 ms 18000 KB Output is correct
9 Correct 5 ms 17488 KB Output is correct
10 Correct 6 ms 17232 KB Output is correct
11 Correct 4 ms 17232 KB Output is correct
12 Correct 5 ms 17704 KB Output is correct
13 Correct 5 ms 17744 KB Output is correct
14 Correct 5 ms 17488 KB Output is correct
15 Correct 5 ms 17656 KB Output is correct
16 Correct 7 ms 18256 KB Output is correct
17 Correct 6 ms 17744 KB Output is correct
18 Correct 4 ms 17156 KB Output is correct
19 Correct 5 ms 17912 KB Output is correct
20 Correct 5 ms 17488 KB Output is correct
21 Correct 4 ms 17488 KB Output is correct
22 Correct 5 ms 17488 KB Output is correct
23 Correct 5 ms 17400 KB Output is correct
24 Correct 5 ms 17744 KB Output is correct
25 Correct 5 ms 17488 KB Output is correct
26 Correct 5 ms 17744 KB Output is correct
27 Correct 6 ms 17744 KB Output is correct
28 Correct 5 ms 17744 KB Output is correct
29 Correct 5 ms 18000 KB Output is correct
30 Correct 5 ms 17968 KB Output is correct
31 Correct 5 ms 18000 KB Output is correct
32 Correct 6 ms 18000 KB Output is correct
33 Correct 227 ms 79636 KB Output is correct
34 Correct 175 ms 54832 KB Output is correct
35 Correct 214 ms 76616 KB Output is correct
36 Correct 148 ms 54856 KB Output is correct
37 Correct 86 ms 35768 KB Output is correct
38 Correct 69 ms 31316 KB Output is correct
39 Correct 105 ms 56648 KB Output is correct
40 Correct 98 ms 56608 KB Output is correct
41 Correct 77 ms 56648 KB Output is correct
42 Correct 100 ms 42692 KB Output is correct
43 Correct 92 ms 42472 KB Output is correct
44 Correct 268 ms 104520 KB Output is correct
45 Correct 164 ms 69036 KB Output is correct
46 Correct 60 ms 31304 KB Output is correct
47 Correct 157 ms 52376 KB Output is correct
48 Correct 96 ms 45640 KB Output is correct
49 Correct 76 ms 45384 KB Output is correct
50 Correct 154 ms 47044 KB Output is correct
51 Correct 70 ms 34500 KB Output is correct
52 Correct 168 ms 53184 KB Output is correct
53 Correct 85 ms 46016 KB Output is correct
54 Correct 87 ms 56644 KB Output is correct
55 Correct 121 ms 54088 KB Output is correct
56 Correct 122 ms 59984 KB Output is correct
57 Correct 119 ms 63048 KB Output is correct
58 Correct 132 ms 60488 KB Output is correct
59 Correct 133 ms 60488 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 6 ms 18000 KB Output is correct
6 Correct 6 ms 17488 KB Output is correct
7 Correct 6 ms 17304 KB Output is correct
8 Correct 7 ms 18000 KB Output is correct
9 Correct 5 ms 17488 KB Output is correct
10 Correct 6 ms 17232 KB Output is correct
11 Correct 4 ms 17232 KB Output is correct
12 Correct 5 ms 17704 KB Output is correct
13 Correct 5 ms 17744 KB Output is correct
14 Correct 5 ms 17488 KB Output is correct
15 Correct 5 ms 17656 KB Output is correct
16 Correct 7 ms 18256 KB Output is correct
17 Correct 6 ms 17744 KB Output is correct
18 Correct 4 ms 17156 KB Output is correct
19 Correct 5 ms 17912 KB Output is correct
20 Correct 5 ms 17488 KB Output is correct
21 Correct 4 ms 17488 KB Output is correct
22 Correct 5 ms 17488 KB Output is correct
23 Correct 5 ms 17400 KB Output is correct
24 Correct 5 ms 17744 KB Output is correct
25 Correct 5 ms 17488 KB Output is correct
26 Correct 5 ms 17744 KB Output is correct
27 Correct 6 ms 17744 KB Output is correct
28 Correct 5 ms 17744 KB Output is correct
29 Correct 5 ms 18000 KB Output is correct
30 Correct 5 ms 17968 KB Output is correct
31 Correct 5 ms 18000 KB Output is correct
32 Correct 6 ms 18000 KB Output is correct
33 Correct 227 ms 79636 KB Output is correct
34 Correct 175 ms 54832 KB Output is correct
35 Correct 214 ms 76616 KB Output is correct
36 Correct 148 ms 54856 KB Output is correct
37 Correct 86 ms 35768 KB Output is correct
38 Correct 69 ms 31316 KB Output is correct
39 Correct 105 ms 56648 KB Output is correct
40 Correct 98 ms 56608 KB Output is correct
41 Correct 77 ms 56648 KB Output is correct
42 Correct 100 ms 42692 KB Output is correct
43 Correct 92 ms 42472 KB Output is correct
44 Correct 268 ms 104520 KB Output is correct
45 Correct 164 ms 69036 KB Output is correct
46 Correct 60 ms 31304 KB Output is correct
47 Correct 157 ms 52376 KB Output is correct
48 Correct 96 ms 45640 KB Output is correct
49 Correct 76 ms 45384 KB Output is correct
50 Correct 154 ms 47044 KB Output is correct
51 Correct 70 ms 34500 KB Output is correct
52 Correct 168 ms 53184 KB Output is correct
53 Correct 85 ms 46016 KB Output is correct
54 Correct 87 ms 56644 KB Output is correct
55 Correct 121 ms 54088 KB Output is correct
56 Correct 122 ms 59984 KB Output is correct
57 Correct 119 ms 63048 KB Output is correct
58 Correct 132 ms 60488 KB Output is correct
59 Correct 133 ms 60488 KB Output is correct
60 Correct 4 ms 16720 KB Output is correct
61 Incorrect 3 ms 16720 KB Output isn't correct
62 Halted 0 ms 0 KB -