oj.uz

Submission #1051648

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

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 2 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 339 ms 157264 KB Output is correct
2 Runtime error 1004 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 7772 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 15 ms 20060 KB Output is correct
4 Correct 67 ms 59472 KB Output is correct
5 Runtime error 1162 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 58 ms 23124 KB Output is correct
2 Correct 45 ms 20140 KB Output is correct
3 Correct 55 ms 35664 KB Output is correct
4 Correct 45 ms 30476 KB Output is correct
5 Correct 55 ms 44080 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 2 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 89 ms 42576 KB Output is correct
11 Correct 73 ms 34900 KB Output is correct
12 Correct 203 ms 145264 KB Output is correct
13 Correct 147 ms 143044 KB Output is correct
14 Correct 187 ms 149356 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11352 KB Output is correct
2 Correct 40 ms 21328 KB Output is correct
3 Correct 39 ms 21084 KB Output is correct
4 Correct 44 ms 22344 KB Output is correct
5 Runtime error 901 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 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 2 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 7772 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 15 ms 20060 KB Output is correct
13 Correct 67 ms 59472 KB Output is correct
14 Runtime error 1162 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 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 2 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 339 ms 157264 KB Output is correct
11 Runtime error 1004 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -