Submission #1280240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280240		bjp123	Magic Tree (CEOI19_magictree)	C++20	0 / 100	2016 ms	5760 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;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
cin>>n>>m>>k;
vector<ll>dp(n+1,0),par(n+1),val(n+1,0);
vector<vector<ii>>times(k+1);
for(i=2;i<=n;i++)
{
    cin>>par[i];
    //v[par[i]].pb(i);
}
//dfs(1);
for(i=1;i<=m;i++)
{
    ll u,d,w;
    cin>>u>>d>>w;
    times[d].pb({u,w});
}
for(i=1;i<=k;i++)
{
for(auto [u,w]:times[i])
{
    val[u]=w;
    dp[u]+=w;
    //cout<<dp[1]<<'\n';
    while(u!=1) {
        ll v=par[u],lst=dp[v];
        dp[v]=max(dp[v],dp[v]-val[v]+w);
        //if(u==5) cout<<v<<" "<<w<<" "<<dp[v]<<'\n';
        w=dp[v]-lst;
        if(w==0) break;
        u=v;
    }
}
}
cout<<dp[1];
    return 0;
}
/*
x+[2c(x)+1.5)
=(c(x)+1)^2 +.5
*/

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