Submission #1280293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280293		bjp123	Magic Tree (CEOI19_magictree)	C++20	100 / 100	164 ms	34040 KiB

magictree

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<ll, ll>
#define all(a) a.begin(), a.end()
#define iii pair<ii, ll>
#define ld long double
using namespace std;

const ll N = 1e5 + 5;
const ll mod = 1e9+7;
const ll inf=4e18+3;
const ld expp=1e-12;
ll n, m, i, j, k, t, q,x,c;

/// s cointain  {day,update}
multiset<ii> s[N];
vector<ll> v[N];
ll d[N],w[N];
void dfs(ll u)
{
    for(auto x:v[u])
    {
        dfs(x);
        if(s[x].size()>s[u].size()) swap(s[x],s[u]);
        for(auto tmp:s[x]) s[u].insert(tmp);
        s[x].clear();
    }
    //cout<<u<<" "<<s[u].size()<<" "<<d[u]<<'\n';
    if(!d[u]) return ;
    s[u].insert({d[u],w[u]});
    auto it=s[u].upper_bound({d[u],inf}),en=it;
    ll sum=0;
    for(;en!=s[u].end();++en)
    {
        sum+=en->se;
        if(sum>w[u]) break;
    }
    if(en==s[u].end())
    {
        s[u].erase(it,en);
        return ;
    }
    ii tmp=*en;
    ++en;
    s[u].erase(it,en);
    if(sum>w[u]) s[u].insert({tmp.fi,sum-w[u]});
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
cin>>n>>m>>k;
for(i=2;i<=n;i++)
{
    cin>>x;
    v[x].pb(i);
}
memset(d,0,sizeof(d));
for(i=1;i<=m;i++)
{
    ll u,day,wei;
    cin>>u>>day>>wei;
    d[u]=day;
    w[u]=wei;
}
dfs(1);
ll res=0;
for(auto x:s[1]) res+=x.se;
cout<<res;
    return 0;
}
/*
10 9 10
1
1
2
2
3
1
3
8
3
5 4 1
9 4 1
6 8 1
3 1 1
4 9 1
10 1 1
2 6 1
8 7 1
7 9 1
*/

• 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