답안 #1049130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049130	2024-08-08T13:45:50 Z	anton	Magic Tree (CEOI19_magictree)	C++17	9 / 100	108 ms	80008 KB

magictree

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
int N, M, K;
const int INF= 1e2;

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

struct Node{
    int l = 0, r = 0;
    int lazy = 0, v = 0;
    int sz = 0;
    Node(int _l, int _r){
        l = _l;
        r= _r;
    }
};
struct HollowTree{
    vector<Node> tr;

    HollowTree(){
        tr.resize(2, Node(0, 0));
    }

    Node get_node(int l, int r){
        Node res= Node(l, r);
        res.v = max(tr[l].v, tr[r].v);
        return res;
    }

    void upd(int i){
        tr[i].v = max(tr[tr[i].l].v, tr[tr[i].r].v) + tr[i].lazy;
        tr[i].sz = tr[tr[i].l].sz + tr[tr[i].r].sz;
    }

    void propagate(int t){
        if(tr[t].l == 0){
            tr[t].l = tr.size();
            tr.push_back(Node(0, 0));
        }
        if(tr[t].r == 0){
            tr[t].r = tr.size();
            tr.push_back(Node(0, 0));
        }
    }

    void insert(int pos, int v, int lt, int rt, int t){
        if(lt == rt){
            tr[t].lazy = v;
            tr[t].v = v;
            tr[t].sz = 1;
        }
        else{
            propagate(t);
            int mid = (lt+rt)/2;
            if(pos<=mid){
                insert(pos, v-tr[t].lazy, lt, mid, tr[t].l);
            }
            else{
                insert(pos, v-tr[t].lazy, mid+1, rt, tr[t].r);
            }
            upd(t);
        }
    }

    void add(int l, int r, int v, int lt, int rt, int t){
        if(l<= lt && rt <= r){
            tr[t].lazy +=v;
            tr[t].v+=v;
        }
        else if(r<lt || rt <l){
            return;
        }
        else{
            int mid = (lt+rt)/2;
            propagate(t);
            add(l, r, v, lt, mid, tr[t].l);
            add(l, r, v, mid+1, rt, tr[t].r);
            upd(t);
        }
    }

    int get(int l, int r, int lt, int rt, int t){
        if(l<= lt && rt <= r){
            return tr[t].v;
        }
        else if(r<lt || rt <l){
            return 0;
        }
        else{
            int mid = (lt+rt)/2;
            propagate(t);
            return max(get(l, r, lt, mid, tr[t].l), get(l, r, mid+1, rt, tr[t].r)) + tr[t].lazy;
        }
    }

    void iterate(vector<pii>& res,int lazy,  int lt, int rt, int t){
        if(lt == rt){
            if(res.size()==0 || tr[t].v+ lazy>= res.back().second){
                res.push_back({lt, tr[t].v+ lazy});
            }
        }
        else{
            int mid =(lt+rt)/2;
            propagate(t);
            if(tr[tr[t].l].sz>0){
                iterate(res, lazy +tr[t].lazy,lt, mid, tr[t].l);
            }
            if(tr[tr[t].r].sz>0){
                iterate(res,lazy +tr[t].lazy, mid+1, rt, tr[t].r);
            }
        }
    }
    void merge(HollowTree& rh){
        vector<pii> rh_e;
        rh.iterate(rh_e, 0, 0, INF,1);
        int prev= 0;
        
        for(auto e: rh_e){
            int max_before = get(0, e.first, 0, INF, 1);
            insert(e.first, max_before, 0, INF, 1);
            prev = e.second;
        }
        prev= 0;
        int prev_pos = 0;
        for(auto e: rh_e){
            add(prev_pos, e.first-1, prev, 0, INF, 1);
            prev_pos = e.first;
            prev= e.second;
        }
        add(prev_pos, INF, prev, 0, INF, 1);
    }

    void display(){
        vector<pii> res;
        iterate(res, 0, 0, INF, 1);
        for(auto e: res){
            cout<<e.first<<" "<<e.second<<endl;
        }
    }
};

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



void dfs2(int u, int fruit_anc){
    if(vertex_fruit[u].pos != -1){
        fruit_ch[fruit_anc].push_back(u);
        fruit_anc = u;
    }
    for(auto e: ch[u]){
        dfs2(e, fruit_anc);
    }
}

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


vector<HollowTree> trees;
void dfs(int u){
    for(auto e: fruit_ch[u]){
        dfs(e);
        if(trees[e].tr.size()>trees[u].tr.size()){
            swap(trees[e], trees[u]);
        }
        trees[u].merge(trees[e]);
    }

    if(vertex_fruit[u].pos != -1){
        int max_before = trees[u].get(0, vertex_fruit[u].t, 0, INF, 1);
        trees[u].insert(vertex_fruit[u].t, max_before+vertex_fruit[u].w, 0, INF, 1);
    }

    //cout<<"tree "<<u+1<<endl;
    //trees[u].display();
}

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

    trees.resize(N);

    vertex_fruit.resize(N, Fruit(-1, -1, -1));
    ch.resize(N);
    fruit_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);

    dfs2(0, 0);
    dfs(0);

    cout<<trees[0].get(0, INF, 0, INF, 1)<<endl;
}

Compilation message

magictree.cpp: In function 'long long int find_pos(std::vector<long long int>&, long long int)':
magictree.cpp:175: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]
  175 |         if(cur + step<v.size()){
      |            ~~~~~~~~~~^~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	344 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	39652 KB	Output is correct
2	Correct	37 ms	37604 KB	Output is correct
3	Correct	108 ms	80008 KB	Output is correct
4	Correct	86 ms	78592 KB	Output is correct
5	Correct	105 ms	79040 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	1624 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	93 ms	59612 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	94 ms	59096 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	5212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	1 ms	1624 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	49 ms	39652 KB	Output is correct
11	Correct	37 ms	37604 KB	Output is correct
12	Correct	108 ms	80008 KB	Output is correct
13	Correct	86 ms	78592 KB	Output is correct
14	Correct	105 ms	79040 KB	Output is correct
15	Incorrect	1 ms	1624 KB	Output isn't correct
16	Halted	0 ms	0 KB	-