oj.uz

Submission #990341

# Submission time Handle Problem Language Result Execution time Memory
990341 2024-05-30T08:45:09 Z imarn Magic Tree (CEOI19_magictree) C++14
100 / 100
 1360 ms 38400 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=1e5+5;
int d[mxn]{0};ll w[mxn];
map<int,ll>dp[mxn];
vector<int>g[mxn];
void dfs(int u){
    for(auto v:g[u]){
        dfs(v);
        if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]);
        for(auto it:dp[v]){
            if(dp[u].find(it.f)!=dp[u].end())dp[u][it.f]+=it.s;
            else dp[u][it.f]=it.s;
        }
    }
    if(d[u]==0)return;
    if(dp[u].find(d[u])==dp[u].end())dp[u][d[u]]=w[u];
    else dp[u][d[u]]+=w[u];
    ll cur=w[u];
    auto it = dp[u].upper_bound(d[u]);
    for(;it!=dp[u].end();it++){
        if(cur>=it->s){
            cur-=it->s;
            dp[u][it->f]=0;
        }
        else {
            dp[u][it->f]-=cur;
            break;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    for(int i=2;i<=n;i++){
        int p;cin>>p;g[p].pb(i);
    }
    for(int i=1;i<=m;i++){
        int v;cin>>v;cin>>d[v]>>w[v];
    }dfs(1);ll ans=0;
    for(auto it : dp[1])ans+=it.s;
    cout<<ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 17628 KB Output is correct
2 Correct 29 ms 18204 KB Output is correct
3 Correct 112 ms 34896 KB Output is correct
4 Correct 57 ms 18176 KB Output is correct
5 Correct 96 ms 19712 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 220 ms 30144 KB Output is correct
5 Correct 64 ms 30036 KB Output is correct
6 Correct 1360 ms 30136 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13916 KB Output is correct
2 Correct 42 ms 15116 KB Output is correct
3 Correct 36 ms 19352 KB Output is correct
4 Correct 26 ms 16348 KB Output is correct
5 Correct 34 ms 26196 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 47 ms 19540 KB Output is correct
11 Correct 40 ms 18212 KB Output is correct
12 Correct 34 ms 18628 KB Output is correct
13 Correct 24 ms 15596 KB Output is correct
14 Correct 32 ms 25620 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8028 KB Output is correct
2 Correct 16 ms 10816 KB Output is correct
3 Correct 14 ms 10844 KB Output is correct
4 Correct 16 ms 11100 KB Output is correct
5 Correct 7 ms 9276 KB Output is correct
6 Correct 18 ms 13104 KB Output is correct
7 Correct 18 ms 16732 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 220 ms 30144 KB Output is correct
14 Correct 64 ms 30036 KB Output is correct
15 Correct 1360 ms 30136 KB Output is correct
16 Correct 47 ms 19540 KB Output is correct
17 Correct 40 ms 18212 KB Output is correct
18 Correct 34 ms 18628 KB Output is correct
19 Correct 24 ms 15596 KB Output is correct
20 Correct 32 ms 25620 KB Output is correct
21 Correct 22 ms 11608 KB Output is correct
22 Correct 59 ms 20992 KB Output is correct
23 Correct 92 ms 25292 KB Output is correct
24 Correct 118 ms 37972 KB Output is correct
25 Correct 54 ms 19668 KB Output is correct
26 Correct 90 ms 23376 KB Output is correct
27 Correct 191 ms 24916 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 37 ms 17628 KB Output is correct
11 Correct 29 ms 18204 KB Output is correct
12 Correct 112 ms 34896 KB Output is correct
13 Correct 57 ms 18176 KB Output is correct
14 Correct 96 ms 19712 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 220 ms 30144 KB Output is correct
19 Correct 64 ms 30036 KB Output is correct
20 Correct 1360 ms 30136 KB Output is correct
21 Correct 40 ms 13916 KB Output is correct
22 Correct 42 ms 15116 KB Output is correct
23 Correct 36 ms 19352 KB Output is correct
24 Correct 26 ms 16348 KB Output is correct
25 Correct 34 ms 26196 KB Output is correct
26 Correct 47 ms 19540 KB Output is correct
27 Correct 40 ms 18212 KB Output is correct
28 Correct 34 ms 18628 KB Output is correct
29 Correct 24 ms 15596 KB Output is correct
30 Correct 32 ms 25620 KB Output is correct
31 Correct 5 ms 8028 KB Output is correct
32 Correct 16 ms 10816 KB Output is correct
33 Correct 14 ms 10844 KB Output is correct
34 Correct 16 ms 11100 KB Output is correct
35 Correct 7 ms 9276 KB Output is correct
36 Correct 18 ms 13104 KB Output is correct
37 Correct 18 ms 16732 KB Output is correct
38 Correct 22 ms 11608 KB Output is correct
39 Correct 59 ms 20992 KB Output is correct
40 Correct 92 ms 25292 KB Output is correct
41 Correct 118 ms 37972 KB Output is correct
42 Correct 54 ms 19668 KB Output is correct
43 Correct 90 ms 23376 KB Output is correct
44 Correct 191 ms 24916 KB Output is correct
45 Correct 24 ms 11868 KB Output is correct
46 Correct 54 ms 21424 KB Output is correct
47 Correct 63 ms 25580 KB Output is correct
48 Correct 110 ms 38400 KB Output is correct
49 Correct 60 ms 20432 KB Output is correct
50 Correct 98 ms 24260 KB Output is correct
51 Correct 173 ms 25748 KB Output is correct