oj.uz

Submission #1051609

# Submission time Handle Problem Language Result Execution time Memory
1051609 2024-08-10T08:36:49 Z MrAndria Magic Tree (CEOI19_magictree) C++14
34 / 100
 1134 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,ans,d,w,v1,sum[200005],day[200005],x;
map <int,int> dp[200005];
vector <map <int,int> :: iterator> v;
vector <int> adj[200005];

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];
    v.clear();

    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;
        v.pb(it);
        it++;
    }
    for(int i=0;i<v.size();i++){
        dp[x].erase(v[i]);
    }
    dp[x][day[x]]+=sum[x];
    
}
signed main(){
    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;
}

Compilation message

magictree.cpp: In function 'void dfs(long long int, long long int)':
magictree.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::_Rb_tree_iterator<std::pair<const long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 167284 KB Output is correct
2 Runtime error 993 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 3 ms 17240 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 16 ms 29516 KB Output is correct
4 Correct 90 ms 71000 KB Output is correct
5 Runtime error 1134 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 96 ms 33720 KB Output is correct
2 Correct 78 ms 30544 KB Output is correct
3 Correct 79 ms 46672 KB Output is correct
4 Correct 65 ms 40640 KB Output is correct
5 Correct 80 ms 55700 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 3 ms 16984 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16828 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 118 ms 52816 KB Output is correct
11 Correct 93 ms 45084 KB Output is correct
12 Correct 200 ms 155752 KB Output is correct
13 Correct 161 ms 153024 KB Output is correct
14 Correct 186 ms 160592 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21084 KB Output is correct
2 Correct 46 ms 31108 KB Output is correct
3 Correct 38 ms 30804 KB Output is correct
4 Correct 41 ms 32092 KB Output is correct
5 Runtime error 842 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 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 3 ms 16984 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16828 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 3 ms 17240 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 16 ms 29516 KB Output is correct
13 Correct 90 ms 71000 KB Output is correct
14 Runtime error 1134 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 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 3 ms 16984 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16828 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 283 ms 167284 KB Output is correct
11 Runtime error 993 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -