oj.uz

Submission #1051656

# Submission time Handle Problem Language Result Execution time Memory
1051656 2024-08-10T08:52:12 Z MrAndria Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 29428 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];

    dp[x][day[x]]+=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++;
    }
    
}
signed main(){
    scanf("%d%d%d",&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++){
        scanf("%d%d%d",&v1,&d,&w);
        day[v1]=d;
        sum[v1]=w;
    }
    dfs(1,0);
    for(auto u:dp[1]){
        ans+=u.ss;
    }
    cout<<ans<<endl;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d%d",&v1,&d,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 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 170 ms 14528 KB Output is correct
2 Execution timed out 2077 ms 18072 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 7516 KB Output is correct
2 Correct 2 ms 7492 KB Output is correct
3 Correct 8 ms 7516 KB Output is correct
4 Correct 52 ms 28508 KB Output is correct
5 Execution timed out 2086 ms 29428 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 11348 KB Output is correct
2 Correct 39 ms 11352 KB Output is correct
3 Correct 43 ms 18044 KB Output is correct
4 Correct 35 ms 11612 KB Output is correct
5 Correct 47 ms 28496 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 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 61 ms 11356 KB Output is correct
11 Correct 47 ms 11508 KB Output is correct
12 Correct 93 ms 18264 KB Output is correct
13 Correct 84 ms 11728 KB Output is correct
14 Correct 94 ms 28508 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 29 ms 11532 KB Output is correct
3 Correct 28 ms 11356 KB Output is correct
4 Correct 29 ms 11612 KB Output is correct
5 Correct 1833 ms 11804 KB Output is correct
6 Correct 546 ms 15004 KB Output is correct
7 Correct 236 ms 18264 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 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 7516 KB Output is correct
11 Correct 2 ms 7492 KB Output is correct
12 Correct 8 ms 7516 KB Output is correct
13 Correct 52 ms 28508 KB Output is correct
14 Execution timed out 2086 ms 29428 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 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 170 ms 14528 KB Output is correct
11 Execution timed out 2077 ms 18072 KB Time limit exceeded
12 Halted 0 ms 0 KB -