Submission #966551

#TimeUsernameProblemLanguageResultExecution timeMemory
966551vjudge1Magic Tree (CEOI19_magictree)C++17
15 / 100
110 ms32596 KiB
#include<bits/stdc++.h> using namespace std; #define N 7<<14 #define int long long vector<int>adj[N]; map<int,int> dp[N]; int d[N],w[N]; void dfs(int n){ dp[n][0]; for(auto i:adj[n]){ dfs(i); if(size(dp[n])<size(dp[i])) swap(dp[n],dp[i]); for(auto&[i,j]:dp[i]) dp[n][i]+=j; dp[i].clear(); } if(w[n]){ dp[n][d[n]]+=w[n]; auto it=dp[n].upper_bound(d[n]); while(it!=dp[n].end()){ if(it->second<=w[n]) it=next(it),dp[n].erase(prev(it)); else { it->second-=w[n]; break; } } } } signed main(){ cin.tie(0)->sync_with_stdio(0); int n,m,k,Q; cin>>n>>m>>k; for(int i=2;i<=n;i++) cin>>Q,adj[Q].push_back(i); while(m--){ int a,b,c; cin>>a>>b>>c; d[a]=b,w[a]=c; } dfs(1); int ans=0; for(auto&[i,j]:dp[1]) ans+=j; cout<<ans; }
#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...