Submission #1203978

#TimeUsernameProblemLanguageResultExecution timeMemory
1203978irmuunMagic Tree (CEOI19_magictree)C++20
0 / 100
2096 ms21184 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(); map<ll,ll>dp[n+5]; map<ll,ll>add; for(ll i=n;i>=1;i--){ ll sz=0,id=-1; for(ll j:g[i]){ if(dp[j].size()>sz){ sz=dp[j].size(); id=j; } } if(id>-1){ swap(dp[i],dp[id]); } add.clear(); for(auto x:dp[i]){ add[x.ff]=0; } for(ll j:g[i]){ if(j==-id) continue; ll bef=0; for(auto x:dp[j]){ add[x.ff]+=x.ss-bef; bef=x.ss; } } ll tot=0,mxx=0; for(auto x:add){ tot+=x.ss; mxx=max(mxx,dp[i][x.ff]); dp[i][x.ff]=tot+mxx; } if(day[i]>0){ dp[i][day[i]]+=pt[i]; } ll mx=0; for(auto &p:dp[i]){ mx=max(mx,p.ss); p.ss=max(p.ss,mx); } if(i==1){ cout<<mx; return 0; } } }
#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...