Submission #1078317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078317		vjudge1	Magic Tree (CEOI19_magictree)	C++14	100 / 100	135 ms	39236 KiB

magictree

#include<bits/stdc++.h>
#define newl '\n'

const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

//struct Node{
//    long long val,lazy;
//    Node() : val(0),lazy(0){
//
//    }
//    Node(long long val,long long lazy) : val(val),lazy(lazy){
//
//    }
//};
//struct SegmentTree{
//    std::vector<Node> st;
//    SegmentTree(int n) : st(n * 4 + 10,Node()){
//
//    }
//    void down(int id){
//        st[id << 1].val += st[id].lazy;
//        st[id << 1].lazy += st[id].lazy;
//        st[id << 1 | 1].val += st[id].lazy;
//        st[id << 1 | 1].lazy += st[id].lazy;
//        st[id].lazy = 0;
//    }
//    void update(int l,int r,int u,int v,long long val,int id = 1){
//        if(u <= l && r <= v){
//            st[id].val += val;
//            st[id].lazy += val;
//            return;
//        }
//        down(id);
//        int mid = (l + r) / 2;
//        if(v <= mid){
//            update(l,mid,u,v,val,id << 1);
//        }
//        if(u > mid){
//            update(mid + 1,r,u,v,val,id << 1 | 1);
//        }
//        update(l,mid,u,v,val,id << 1);
//        update(mid + 1,r,u,v,val,id << 1 | 1);
//        st[id].val = std::max(st[id << 1].val,st[id << 1 | 1].val);
//    }
//    long long get(int l,int r,int u,int v,int id = 1){
//        if(u <= l && r <= v){
//            return st[id].val;
//        }
//        int mid = (l + r) / 2;
//        if(v <= mid){
//            return get(l,mid,u,v,id << 1);
//        }
//        if(u > mid){
//            return get(mid + 1,r,u,v,id << 1 | 1);
//        }
//        return std::max(get(l,mid,u,v,id << 1),get(mid + 1,r,u,v,id << 1 | 1));
//    }
//};
struct BIT{
    std::vector<long long> bit;
    BIT(int n) : bit(n + 1,0){

    }
    void update(int idx,long long val){
        for(int i = idx;i < (int)bit.size();i += (i & (-i))){
            bit[i] += val;
        }
    }
    long long get(int idx){
        long long ans = 0;
        for(int i = idx;i > 0;i -= (i & (-i))){
            ans += bit[i];
        }
        return ans;
    }
//    void updR(int l,int r){
//        update(l,val);
//        update(r + 1,-val);
//    }
};
std::vector<int> adj[N + 1];
bool mark[N + 1];
std::map<int,long long> diff[N + 1];

int n,m,k,d[N + 1],w[N + 1],in[N + 1],out[N + 1],ver[N + 1],f[N + 1],timer = 0;
long long s[N + 1];

void readData(){
    std::cin >> n >> m >> k;
    std::fill(d + 1,d + n + 1,k);
    for(int i = 2;i <= n;++i){
        int p;
        std::cin >> p;
        adj[p].emplace_back(i);
    }
    for(int i = 1;i <= m;++i){
        int v;
        std::cin >> v;
        std::cin >> d[v] >> w[v];
    }
}
void gs(int u = 1){
    f[u] = 1;
    in[u] = ++timer;
    ver[in[u]] = u;
    for(int &v : adj[u]){
        gs(v);
        f[u] += f[v];
        if(f[v] > f[adj[u][0]]){
            std::swap(v,adj[u][0]);
        }
    }
    out[u] = timer;
}
void solve(){
    BIT bit(k);
    auto add = [&](int i,long long val,std::map<int,long long> &mm){
        long long s = bit.get(i);
        long long upd = val - s,t = 0;
        auto it = mm.upper_bound(i);
        std::vector<std::pair<int,long long>> v;
        if(upd < 0){
            return;
        }
        it = mm.insert(it,{i,0});
        mm[i] += upd;
        while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
            t += next(it)->second;
            v.emplace_back(*next(it));
            mm.erase(next(it));
        }
        for(auto t : v){
            bit.update(t.first,-t.second);
        }
        bit.update(i,upd);
        if(next(it) != mm.end()){
            bit.update(next(it)->first,-upd);
            bit.update(next(it)->first,t);
            next(it)->second -= upd;
            next(it)->second += t;
        }
    };
    auto remov = [&](std::map<int,long long> &mm) -> void{
        for(auto t : mm){
            bit.update(t.first,-t.second);
        }
    };
    auto merg = [&](std::map<int,long long> &mm,std::map<int,long long> &mm1){
        for(auto t : mm1){
            mm[t.first] += t.second;
            bit.update(t.first,t.second);
        }
    };
    auto dfs = [&](auto &self,int u) -> void{
        for(int v : adj[u]){
            if(v == adj[u][0]){
                continue;
            }
            self(self,v);
            remov(diff[v]);
        }
        if((int)adj[u].size()){
            self(self,adj[u][0]);
            std::swap(diff[u],diff[adj[u][0]]);
        }
        for(int v : adj[u]){
            if(v == adj[u][0]){
                continue;
            }
            merg(diff[u],diff[v]);
        }
//        if(u == 2){
//            for(int i = 1;i <= k;++i){
//                std::cout << bit.get(i) << " ";
//            }
//            std::cout << newl;
//            for(auto t : diff[u]){
//                std::cerr << t.first << " " << t.second << newl;
//            }
//            std::cout << newl;
//        }
//        if(u == 4){
//            std::cerr << "U = " << u << newl;
//            for(int i = 1;i <= k;++i){
//                std::cerr << bit.get(i) << " ";
//            }
//            std::cerr << newl;
//            for(auto t : diff[u]){
//                std::cerr << t.first << " " << t.second << newl;
//            }
//            std::cerr << newl;
//        }
        s[u] = bit.get(d[u]) + w[u];
        add(d[u],s[u],diff[u]);
//        if(u == 4){
//            std::cerr << "U = " << u << newl;
//            for(int i = 1;i <= k;++i){
//                std::cerr << bit.get(i) << " ";
//            }
//            std::cerr << newl;
//            for(auto t : diff[u]){
//                std::cerr << t.first << " " << t.second << newl;
//            }
//            std::cerr << newl;
//        }
    };
    dfs(dfs,1);
//    for(int i = 1;i <= n;++i){
//        std::cout << i << " " << w[i] << newl;
//    }
    std::cout << bit.get(k);
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    gs();
    solve();
//    std::map<int,long long> mm;
//    BIT bit(5);
//    auto add = [&](int i,long long val){
//        long long s = bit.get(i);
//        long long upd = val - s,t = 0;
//        auto it = mm.upper_bound(i);
//        if(upd < 0){
//            return;
//        }
//        it = mm.insert(it,{i,0});
//        mm[i] += upd;
//        while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
//            t += next(it)->second;
//            bit.update(next(it)->first,-next(it)->second);
//            mm.erase(next(it));
//        }
//        bit.update(i,upd);
//        if(next(it) != mm.end()){
//            bit.update(next(it)->first,-upd);
//            bit.update(next(it)->first,t);
//            next(it)->second -= upd;
//            next(it)->second += t;
//        }
//    };
//    add(1,3);
//    for(auto t : mm){
//        std::cout << t.second << " ";
//    }
//    std::cout << newl;
//    add(1,9);
//    add(1,7);
//    add(1,10);
//    add(1,5);
//    add(2,12);
//    add(1,13);
//    add(5,15);
//    add(3,19);
//    add(2,20);
//    std::cout << bit.get(2) << newl;
//    std::cout << newl;
//    for(auto t : mm){
//        std::cout << t.second << " ";
//    }
//    std::cout << newl;
//    add(1,10);
//    add(1,10);
//    add(5,15);
//    add(3,30);
//    add(2,20);
//    std::cout << bit.get(4) << newl;
//    for(auto t : mm){
//        std::cout << t.second << " ";
//    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17