oj.uz

Submission #1048600

# Submission time Handle Problem Language Result Execution time Memory
1048600 2024-08-08T08:37:35 Z anton Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
int N, M, K;


struct Fruit{
    int pos = -1, t, w;
    Fruit(){};
    Fruit(int _pos, int _t, int _w){
        pos = _pos;
        t= _t;
        w =_w;
    }
};

vector<Fruit> fr;
vector<Fruit> vertex_fruit;
vector<int> anc;
vector<vector<int>> ch;

vector<int> merge(vector<int> lh, vector<int> rh){
    int lmax= 0, rmax = 0;
    vector<int> res(K+1);
    for(int i = 0; i<=K; i++){
        lmax = max(lmax, lh[i]);
        rmax = max(rmax, rh[i]);
        res[i] = rmax+lmax;
    }
    return res;
}
vector<int> dfs(int u, int anc){
    vector<int> res(K+1);
    for(auto e: ch[u]){
        vector<int> ch_res = dfs(e, u);
        res=  merge(res, ch_res);
    }

    if(vertex_fruit[u].pos != -1){
        int best= 0;
        for(int i = 0; i<=vertex_fruit[u].t; i++){
            best = max(best, res[i]);
        }

        res[vertex_fruit[u].t] = best+vertex_fruit[u].w;
    }

    /*cout<<"res "<<u<<endl;
    for(int i = 0; i<=K; i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;*/
    return res;
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N>>M>>K;

    vertex_fruit.resize(N, Fruit(-1, -1, -1));
    ch.resize(N);

    anc.resize(N);
    for(int  i= 1; i<N; i++){
        cin>>anc[i];
        anc[i]--;
        ch[anc[i]].push_back(i);
    }
    for(int i = 0; i<M; i++){
        int v, d, w;
        cin>>v>>d>>w;
        v--;
        fr.push_back(Fruit(v, d, w));
        vertex_fruit[v]= fr.back();
    }


    vector<int> RES = dfs(0, -1);
    int ans= 0;
    for(int i = 0; i<=K; i++){
        ans = max(ans, RES[i]);
    }
    cout<<ans<<endl;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 30560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8404 KB Output is correct
2 Correct 9 ms 8584 KB Output is correct
3 Correct 7 ms 8540 KB Output is correct
4 Runtime error 414 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13404 KB Output is correct
2 Correct 44 ms 12836 KB Output is correct
3 Correct 47 ms 22184 KB Output is correct
4 Correct 33 ms 13268 KB Output is correct
5 Correct 43 ms 36740 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 48 ms 13324 KB Output is correct
11 Correct 41 ms 12180 KB Output is correct
12 Correct 42 ms 26920 KB Output is correct
13 Correct 26 ms 12156 KB Output is correct
14 Correct 55 ms 50160 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2011 ms 12076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 8 ms 8404 KB Output is correct
11 Correct 9 ms 8584 KB Output is correct
12 Correct 7 ms 8540 KB Output is correct
13 Runtime error 414 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Execution timed out 2082 ms 30560 KB Time limit exceeded
11 Halted 0 ms 0 KB -