Submission #1232941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232941		Tenis0206	Magic Tree (CEOI19_magictree)	C++20	34 / 100	2095 ms	32324 KiB

magictree

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;

int n, m, k;
int t[nmax + 5];
vector<int> G[nmax + 5];

int d[nmax + 5], val[nmax + 5];

int dp[nmax + 5][25];

void dfs(int nod)
{
    for(auto it : G[nod])
    {
        dfs(it);
    }
    for(auto it : G[nod])
    {
        for(int i=1;i<=k;i++)
        {
            dp[nod][i] += dp[it][i];
        }
    }
    if(d[nod])
    {
        dp[nod][d[nod]] += val[nod];
        int poz = d[nod] + 1;
        while(poz <= k && dp[nod][d[nod]] > dp[nod][poz])
        {
            dp[nod][poz] = dp[nod][d[nod]];
            ++poz;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)
    {
        cin>>t[i];
        G[t[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int nod;
        cin>>nod;
        cin>>d[nod]>>val[nod];
    }
    dfs(1);
    cout<<dp[1][k]<<'\n';
    return 0;
}

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