oj.uz

Submission #1051636

# Submission time Handle Problem Language Result Execution time Memory
1051636 2024-08-10T08:44:44 Z MrAndria Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 29352 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
// #define int long long
int n,m,k,d,w,v1,sum[100005],day[100005],x;
long long ans;
map <int,long long> dp[100005];
vector <int> adj[100005];

void dfs(int x,int p){
    for(auto u:adj[x]){
        if(u!=p){
            dfs(u,x);
            if(dp[u].size()<dp[x].size()){
                swap(dp[u],dp[x]);
            }
            for(auto l:dp[u]){
                dp[x][l.ff]+=l.ss;
            }
            dp[u].clear();
        }
    }
    k=sum[x];

    auto it=dp[x].upper_bound(day[x]);
    while(true){
        if(it==dp[x].end())break;
        if((*it).ss>k){
            (*it).ss-=k;
            break;
        }
        k-=(*it).ss;
        dp[x].erase(it++);
        // it++;
    }
    dp[x][day[x]]+=sum[x];
    
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n-1;i++){
        cin>>x;
        adj[i+1].pb(x);
        adj[x].pb(i+1);
    }
    for(int i=1;i<=m;i++){
        cin>>v1>>d>>w;
        day[v1]=d;
        sum[v1]=w;
    }
    dfs(1,0);
    for(auto u:dp[1]){
        ans+=u.ss;
    }
    cout<<ans<<endl;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 14276 KB Output is correct
2 Execution timed out 2078 ms 17972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 8 ms 7772 KB Output is correct
4 Correct 44 ms 28608 KB Output is correct
5 Execution timed out 2099 ms 29352 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11352 KB Output is correct
2 Correct 29 ms 11356 KB Output is correct
3 Correct 35 ms 18268 KB Output is correct
4 Correct 26 ms 11728 KB Output is correct
5 Correct 36 ms 28500 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 45 ms 11356 KB Output is correct
11 Correct 38 ms 11520 KB Output is correct
12 Correct 90 ms 18292 KB Output is correct
13 Correct 75 ms 11732 KB Output is correct
14 Correct 81 ms 28600 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 22 ms 11608 KB Output is correct
3 Correct 22 ms 11612 KB Output is correct
4 Correct 25 ms 11576 KB Output is correct
5 Correct 1785 ms 11840 KB Output is correct
6 Correct 530 ms 14936 KB Output is correct
7 Correct 208 ms 18268 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 2 ms 7512 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 8 ms 7772 KB Output is correct
13 Correct 44 ms 28608 KB Output is correct
14 Execution timed out 2099 ms 29352 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7260 KB Output is correct
10 Correct 159 ms 14276 KB Output is correct
11 Execution timed out 2078 ms 17972 KB Time limit exceeded
12 Halted 0 ms 0 KB -