Submission #1334900

#TimeUsernameProblemLanguageResultExecution timeMemory
1334900sash01Magic Tree (CEOI19_magictree)C++20
100 / 100
100 ms40900 KiB
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <set>
#include <cstring>
#define control cout<<"e ne"<<endl;
#define endl '\n'
#define int long long
using namespace std;
int n,M,k,mx,where[131072],d[131072],w[131072],p[131072],used[131072],parents[131072];
vector <int> v[131072];
pair <int,int> info[131072];
map <int,int> m[131072];
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}
void _merge(int beg,int nb)
{
    if(m[beg].size()<m[nb].size())m[beg].swap(m[nb]);
    for(auto [key,value]:m[nb])
    {
        m[beg][key]+=value;
    }
}
void dfs(int beg,int par)
{
    for(auto nb:v[beg])
    {
        if(nb!=par)
        {
            dfs(nb,beg);
        }
    }
    for(auto nb:v[beg])
    {
        if(nb!=par)
        {
            _merge(beg,nb);
        }
    }
    m[beg][info[beg].first]+=info[beg].second;
    if(info[beg].second==0)return;
    int pom=info[beg].second;
    auto it=m[beg].upper_bound(info[beg].first);
    while(it!=m[beg].end()&&pom>0)
    {
        int x=it->second;
        int mn=min(x,pom);
        it->second-=mn;
        pom-=mn;
        if(pom==0)break;
        m[beg].erase(it);
        it=m[beg].upper_bound(info[beg].first);
    }
}
signed main()
{
    /*
    #ifdef ONLINE_JUDGE
    freopen("txt.in","r",stdin)
    freopen("txt.out","w",stdout)
    #endif
    */
    speed();
    cin>>n>>M>>k;
    for(int i=2; i<=n; i++)
    {
        cin>>parents[i];
        v[parents[i]].push_back(i);
    }
    for(int i=1; i<=M; i++)
    {
        cin>>where[i]>>d[i]>>w[i];
        info[where[i]]= {d[i],w[i]};
    }
    dfs(1,-1);
    for(auto [key,value]:m[1])mx+=value;
    cout<<mx<<endl;
    return 0;
}
/*
6 4 10
1
2
1
4
4
3 1 5
4 2 2
5 1 1
6 2 3
*/
#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...