제출 #1327375

#제출 시각아이디문제언어결과실행 시간메모리
1327375khanhphucscratchMagic Tree (CEOI19_magictree)C++20
3 / 100
178 ms69844 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
multiset<pair<int, int>> st[100005];
void unite(int u, int v)
{
    if(st[u].size() < st[v].size()) st[u].swap(st[v]);
    for(auto i : st[v]) st[u].insert(i);
}
vector<int> ad[100005];
int d[100005], w[100005];
void dfs(int u)
{
    st[u].insert(make_pair(1e18, 1e18));
    for(int v : ad[u]){
        dfs(v); unite(u, v);
    }
    //Now add
    if(w[u] == 0) return;
    int sum = 0;
    multiset<pair<int, int>>::iterator it = st[u].lower_bound(make_pair(d[u], -1));
    while(true){
        if((*it).second + sum > w[u]){
            pair<int, int> target = *it;
            target.second -= w[u] - sum;
            st[u].erase(it);
            st[u].insert(target); break;
        }
        st[u].erase(it++);
    }
    st[u].insert(make_pair(d[u], w[u]));
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, day; cin>>n>>m>>day;
    for(int i = 2; i <= n; i++){
        int p; cin>>p; ad[p].push_back(i);
    }
    for(int i = 1; i <= m; i++){
        int u; cin>>u; cin>>d[u]>>w[u];
    }
    dfs(1);
    int ans = 0;
    for(auto i : st[1]) if(i.first <= day) ans += i.second;
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...