Submission #1051636

#TimeUsernameProblemLanguageResultExecution timeMemory
1051636MrAndriaMagic Tree (CEOI19_magictree)C++14
47 / 100
2099 ms29352 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back // #define int long long int n,m,k,d,w,v1,sum[100005],day[100005],x; long long ans; map <int,long long> dp[100005]; vector <int> adj[100005]; void dfs(int x,int p){ for(auto u:adj[x]){ if(u!=p){ dfs(u,x); if(dp[u].size()<dp[x].size()){ swap(dp[u],dp[x]); } for(auto l:dp[u]){ dp[x][l.ff]+=l.ss; } dp[u].clear(); } } k=sum[x]; auto it=dp[x].upper_bound(day[x]); while(true){ if(it==dp[x].end())break; if((*it).ss>k){ (*it).ss-=k; break; } k-=(*it).ss; dp[x].erase(it++); // it++; } dp[x][day[x]]+=sum[x]; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; for(int i=1;i<=n-1;i++){ cin>>x; adj[i+1].pb(x); adj[x].pb(i+1); } for(int i=1;i<=m;i++){ cin>>v1>>d>>w; day[v1]=d; sum[v1]=w; } dfs(1,0); for(auto u:dp[1]){ ans+=u.ss; } cout<<ans<<endl; }
#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...