Submission #1183445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183445		filipsumic	Magic Tree (CEOI19_magictree)	C++20	100 / 100	177 ms	39516 KiB

magictree

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pi pair<ll, ll>
#define all(x) x.begin(), x.end()

using namespace std;



void DFS(int cvor, int& n, vector<vector<int>>& graf, vector<pi>& voce, vector<multiset<pi>>& promene)
{
    if(graf[cvor].size()==0)
    {
        if(voce[cvor].first!=0 && voce[cvor].second!=0)
            promene[cvor].insert({voce[cvor].first, voce[cvor].second});
        return;
    }
    for(auto u:graf[cvor]) DFS(u, n, graf, voce, promene);
    int tren=graf[cvor][0];
    for(int i=1; i<graf[cvor].size(); i++)
    {
        if(promene[graf[cvor][i]].size()>promene[tren].size())
        {
            for(auto u: promene[tren])
            {
                promene[graf[cvor][i]].insert(u);
            }
            tren=graf[cvor][i];
        }
        else
        {
            for(auto u: promene[graf[cvor][i]]) promene[tren].insert(u);
        }
    }
    promene[cvor]=move(promene[tren]);
    if(voce[cvor].first==0 && voce[cvor].second==0) return;
    else
    {
        ll d=voce[cvor].first;
        ll x=voce[cvor].second;
        promene[cvor].insert({d, x});
        auto it=promene[cvor].upper_bound({d, LLONG_MAX});
        /*if(cvor==5)
            {
                cout<<d<<" "<<x<<"\n";
                cout<<(*it).first<<" "<<(*it).second<<"\n";
            }*/
        ll sum=(*it).second;
        while(it!=promene[cvor].end() && sum<=x)
        {
            auto brisi=it;
            ++it;
            /*if(cvor==5)
            {
                cout<<(*brisi).first<<" "<<(*brisi).second<<"\n";
                cout<<(*it).first<<" "<<(*it).second<<"\n";
            }*/
            promene[cvor].erase(brisi);
            sum+=(*it).second;
        }
        //if(cvor==5) cout<<"skibi\n";
        if(it!=promene[cvor].end())
        {
            ll dv=(*it).first;
            ll pv=(*it).second;
            promene[cvor].insert({dv, sum-pv-x});
        }
    }

}


int main()
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(0);*/

    int n, m, k;
    cin>>n>>m>>k;
    vector<vector<int>> graf(n+5);
    for(int i=2; i<=n; i++)
    {
        int p;
        cin>>p;
        graf[p].pb(i);
    }
    vector<pi> voce(n+5);
    for(int i=1; i<n+1; i++) {voce[i]={0, 0};}
    for(int i=0; i<m; i++)
    {
        ll vj, dj, wj;
        cin>>vj>>dj>>wj;
        voce[vj]={dj, wj};
    }
    vector<multiset<pi>> promene(n+5);
    DFS(1, n, graf, voce, promene);
    ll rez=0;
    for(auto u:promene[1]) rez+=u.second;
    cout<<rez;
}

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