Submission #759368

#	Time	Username	Problem	Language	Result	Execution time	Memory
759368		bgnbvnbv	Magic Tree (CEOI19_magictree)	C++14	100 / 100	95 ms	42956 KiB

magictree

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
#define int ll
vector<ll>g[maxN];
map<int,int>mp[maxN];
ll t[maxN],c[maxN];
void dfs(ll u=1)
{
    for(int v:g[u])
    {
        dfs(v);
        if(mp[v].size()>mp[u].size()) mp[u].swap(mp[v]);
        for(auto zz:mp[v]) mp[u][zz.fi]+=zz.se;
        mp[v].clear();
    }
    if(t[u]>0)
    {
        ll tru=c[u];
        while(tru>0)
        {
            auto it=mp[u].upper_bound(t[u]);
            if(it==mp[u].end()) break;
            if(it->se<=tru)
            {
                tru-=it->se;
                mp[u].erase(it);
            }
            else
            {
                it->se-=tru;
                break;
            }
        }
        mp[u][t[u]]+=c[u];
    }
}
ll n,m,k,p[maxN];
void solve()
{
    cin >> n >> m >> k;
    for(int i=2;i<=n;i++) cin >> p[i],g[p[i]].pb(i);
    while(m--)
    {
        ll u;
        cin >> u;
        cin >> t[u] >> c[u];
    }
    ll ans=0;
    dfs();
    for(auto zz:mp[1]) ans+=zz.se;
    cout << ans;
}
 main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

magictree.cpp:63:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 |  main()
      |  ^~~~

• 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