Submission #1078084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078084		vjudge1	Magic Tree (CEOI19_magictree)	C++14	3 / 100	125 ms	38736 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 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 val[N + 1],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);
        auto it = mm.upper_bound(i);
        if(s >= val){
            return;
        }
        long long upd = val - s;
        it = mm.insert(it,{i,upd});
        if(it->second != upd){
            it->second = upd;
        }
        while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
            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);
        }
    };
    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]);
        }
        s[u] = bit.get(d[u]) + w[u];
        add(d[u],s[u],diff[u]);
    };
    dfs(dfs,1);
    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);
//        auto it = mm.upper_bound(i);
//        if(s >= val){
//            return;
//        }
//        long long upd = val - s;
//        it = mm.insert(it,{i,upd});
//        if(it->second != upd){
//            it->second = upd;
//        }
//        while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
//            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);
//        }
//    };
//    add(1,3);
//    add(2,5);
//    std::cout << bit.get(2) << newl;
//    for(auto t : mm){
//        std::cout << t.second << " ";
//    }
//    std::cout << newl;
//    add(1,10);
//    std::cout << bit.get(1) << newl;
    return 0;
}

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