Submission #1200008

#TimeUsernameProblemLanguageResultExecution timeMemory
1200008irmuunMagic Tree (CEOI19_magictree)C++20
34 / 100
531 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,m,k; cin>>n>>m>>k; vector<ll>g[n+5]; ll p[n+5]; for(ll i=2;i<=n;i++){ cin>>p[i]; g[p[i]].pb(i); } vector<ll>days; ll u[m],d[m],w[m]; vector<ll>day(n+5,0),pt(n+5,0); for(ll i=0;i<m;i++){ cin>>u[i]>>d[i]>>w[i]; day[u[i]]=d[i]; pt[u[i]]=w[i]; days.pb(d[i]); } sort(all(days)); days.erase(unique(all(days)),days.end()); for(ll i=0;i<m;i++){ ll j=lower_bound(all(days),d[i])-days.begin()+1; day[u[i]]=j; } k=days.size(); ll dp[n+5][k+5],pre[n+5][k+5]; memset(dp,0,sizeof dp); memset(pre,0,sizeof pre); for(ll i=n;i>=1;i--){ for(ll j=1;j<=k;j++){ for(ll x:g[i]){ dp[i][j]+=pre[x][j]; } if(day[i]==j){ dp[i][j]+=pt[i]; } } for(ll j=1;j<=k;j++){ pre[i][j]=max(dp[i][j],pre[i][j-1]); } } cout<<pre[1][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...