oj.uz

Submission #1107653

# Submission time Handle Problem Language Result Execution time Memory
1107653 2024-11-01T20:00:15 Z imarn Magic Tree (CEOI19_magictree) C++14
34 / 100
 1659 ms 1048576 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
vector<int>g[mxn];
int d[mxn]{0},w[mxn]{0};
map<int,ll>mp[mxn];
void dfs(int u){
    for(auto v:g[u]){
        dfs(v);
        if(mp[u].size()>mp[v].size())swap(mp[u],mp[v]);
        for(auto it : mp[v])mp[u][it.f]+=it.s;
    }if(d[u]==0)return;
    mp[u][d[u]]+=w[u];int cur=w[u];
    auto it = mp[u].upper_bound(d[u]);
    for(;it!=mp[u].end();){
        if(it->s<=cur){auto ij=it;it++;cur-=ij->s;mp[u].erase(ij);}
        else {it->s-=cur;break;}
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    for(int i=2;i<=n;i++){
        int p;cin>>p;g[p].pb(i);
    }
    for(int i=1;i<=m;i++){
        int v;cin>>v;cin>>d[v]>>w[v];
    }dfs(1);ll rs=0;
    for(auto it : mp[1])rs+=it.s;
    cout<<rs;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 151296 KB Output is correct
2 Runtime error 1578 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 4 ms 8528 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 21 ms 20816 KB Output is correct
4 Correct 86 ms 61308 KB Output is correct
5 Runtime error 1659 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 46 ms 21320 KB Output is correct
2 Correct 39 ms 18000 KB Output is correct
3 Correct 54 ms 31048 KB Output is correct
4 Correct 37 ms 22728 KB Output is correct
5 Correct 55 ms 40132 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8272 KB Output is correct
2 Correct 2 ms 8272 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 2 ms 8272 KB Output is correct
5 Correct 2 ms 8440 KB Output is correct
6 Correct 3 ms 8272 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct
8 Correct 3 ms 8272 KB Output is correct
9 Correct 3 ms 8272 KB Output is correct
10 Correct 102 ms 40008 KB Output is correct
11 Correct 79 ms 32076 KB Output is correct
12 Correct 255 ms 139848 KB Output is correct
13 Correct 198 ms 134856 KB Output is correct
14 Correct 234 ms 144456 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10804 KB Output is correct
2 Correct 30 ms 14032 KB Output is correct
3 Correct 21 ms 13648 KB Output is correct
4 Correct 25 ms 15060 KB Output is correct
5 Runtime error 1271 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 3 ms 8272 KB Output is correct
2 Correct 2 ms 8272 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 2 ms 8272 KB Output is correct
5 Correct 2 ms 8440 KB Output is correct
6 Correct 3 ms 8272 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct
8 Correct 3 ms 8272 KB Output is correct
9 Correct 3 ms 8272 KB Output is correct
10 Correct 4 ms 8528 KB Output is correct
11 Correct 6 ms 9808 KB Output is correct
12 Correct 21 ms 20816 KB Output is correct
13 Correct 86 ms 61308 KB Output is correct
14 Runtime error 1659 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 3 ms 8272 KB Output is correct
2 Correct 2 ms 8272 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 2 ms 8272 KB Output is correct
5 Correct 2 ms 8440 KB Output is correct
6 Correct 3 ms 8272 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct
8 Correct 3 ms 8272 KB Output is correct
9 Correct 3 ms 8272 KB Output is correct
10 Correct 370 ms 151296 KB Output is correct
11 Runtime error 1578 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -