oj.uz

Submission #1051617

# Submission time Handle Problem Language Result Execution time Memory
1051617 2024-08-10T08:39:13 Z MrAndria Magic Tree (CEOI19_magictree) C++14
34 / 100
 1175 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 <map <int,long long> :: iterator> v;
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];
    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(int, int)':
magictree.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::_Rb_tree_iterator<std::pair<const int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7304 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 318 ms 157264 KB Output is correct
2 Runtime error 1008 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 14 ms 20088 KB Output is correct
4 Correct 103 ms 61076 KB Output is correct
5 Runtime error 1175 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 77 ms 23256 KB Output is correct
2 Correct 84 ms 20184 KB Output is correct
3 Correct 78 ms 36176 KB Output is correct
4 Correct 82 ms 30412 KB Output is correct
5 Correct 78 ms 45716 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7304 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 104 ms 42580 KB Output is correct
11 Correct 101 ms 35152 KB Output is correct
12 Correct 208 ms 145744 KB Output is correct
13 Correct 156 ms 143168 KB Output is correct
14 Correct 185 ms 150840 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11356 KB Output is correct
2 Correct 50 ms 21176 KB Output is correct
3 Correct 36 ms 21076 KB Output is correct
4 Correct 40 ms 22300 KB Output is correct
5 Runtime error 813 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 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7304 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 14 ms 20088 KB Output is correct
13 Correct 103 ms 61076 KB Output is correct
14 Runtime error 1175 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 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7304 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 318 ms 157264 KB Output is correct
11 Runtime error 1008 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -