Submission #1048616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1048616	2024-08-08T08:43:16 Z	anton	Magic Tree (CEOI19_magictree)	C++17	13 / 100	2000 ms	1048576 KB

magictree

#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;
}

int find_pos(vector<int> &v, int e){
    int cur =0;
    for(int step = (1<<20); step>=1; step/=2){
        if(cur + step<v.size()){
            if(v[cur+step]<=e){
                cur+=step;
            }
        }
    }
    return cur;
}

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);
    }

    vector<int> times;
    for(int i = 0; i<M; i++){
        int v, d, w;
        cin>>v>>d>>w;
        v--;
        times.push_back(d);
        fr.push_back(Fruit(v, d, w));
    }

    sort(times.begin(), times.end());

    for(Fruit& f: fr){
        f.t = find_pos(times, f.t);
        vertex_fruit[f.pos] = f;
    }
    K = min(K, M);


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

Compilation message

magictree.cpp: In function 'long long int find_pos(std::vector<long long int>&, long long int)':
magictree.cpp:61:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(cur + step<v.size()){
      |            ~~~~~~~~~~^~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	420 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4700 KB	Output is correct
2	Correct	5 ms	4700 KB	Output is correct
3	Correct	4 ms	4572 KB	Output is correct
4	Runtime error	339 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	33 ms	21464 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 16.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	420 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2140 KB	Output is correct
2	Correct	114 ms	8008 KB	Output is correct
3	Correct	125 ms	8536 KB	Output is correct
4	Correct	143 ms	8644 KB	Output is correct
5	Correct	135 ms	7128 KB	Output is correct
6	Correct	376 ms	169228 KB	Output is correct
7	Correct	605 ms	331020 KB	Output is correct

Subtask #7
0 / 22.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	420 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	420 KB	Output isn't correct
5	Halted	0 KB	-