oj.uz

Submission #1051653

# Submission time Handle Problem Language Result Execution time Memory
1051653 2024-08-10T08:51:42 Z MrAndria Magic Tree (CEOI19_magictree) C++14
34 / 100
 1802 ms 1048576 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][l.ff]=0;
            }
        }
    }
    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:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d%d",&v1,&d,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 408 ms 157268 KB Output is correct
2 Runtime error 1558 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 19 ms 20196 KB Output is correct
4 Correct 82 ms 61124 KB Output is correct
5 Runtime error 1802 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23120 KB Output is correct
2 Correct 47 ms 20060 KB Output is correct
3 Correct 56 ms 36312 KB Output is correct
4 Correct 39 ms 30412 KB Output is correct
5 Correct 58 ms 45652 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 116 ms 42464 KB Output is correct
11 Correct 82 ms 34900 KB Output is correct
12 Correct 228 ms 145728 KB Output is correct
13 Correct 159 ms 143004 KB Output is correct
14 Correct 186 ms 150792 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11496 KB Output is correct
2 Correct 46 ms 21148 KB Output is correct
3 Correct 40 ms 21100 KB Output is correct
4 Correct 55 ms 22420 KB Output is correct
5 Runtime error 1031 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 7768 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 19 ms 20196 KB Output is correct
13 Correct 82 ms 61124 KB Output is correct
14 Runtime error 1802 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 408 ms 157268 KB Output is correct
11 Runtime error 1558 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -