oj.uz

Submission #1078084

# Submission time Handle Problem Language Result Execution time Memory
1078084 2024-08-27T12:28:30 Z vjudge1 Magic Tree (CEOI19_magictree) C++14
3 / 100
 125 ms 38736 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 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21776 KB Output is correct
2 Correct 40 ms 24400 KB Output is correct
3 Correct 125 ms 38736 KB Output is correct
4 Correct 57 ms 23132 KB Output is correct
5 Correct 85 ms 25428 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 18268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -