oj.uz

답안 #1078183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078183 2024-08-27T13:41:06 Z vjudge1 Magic Tree (CEOI19_magictree) C++14
15 / 100
 127 ms 36760 KB 
#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);
        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;
        }
    };
    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 == 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);
    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(val   < 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);
////    std::cout << bit.get(2) << newl;
////    std::cout << newl;
////    for(auto t : mm){
////        std::cout << t.second << " ";
////    }
////    std::cout << newl;
////    add(1,10);
//    std::cout << bit.get(4) << newl;
//    for(auto t : mm){
//        std::cout << t.second << " ";
//    }
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 23124 KB Output is correct
2 Correct 39 ms 22608 KB Output is correct
3 Correct 127 ms 36760 KB Output is correct
4 Correct 65 ms 21712 KB Output is correct
5 Correct 85 ms 22868 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16212 KB Output is correct
2 Correct 44 ms 15188 KB Output is correct
3 Correct 41 ms 20464 KB Output is correct
4 Correct 32 ms 17104 KB Output is correct
5 Correct 43 ms 29268 KB Output is correct

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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