Submission #980506

#TimeUsernameProblemLanguageResultExecution timeMemory
980506happy_nodeWorst Reporter 4 (JOI21_worst_reporter4)C++17
79 / 100
284 ms59572 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=2e5+5; int N; int A[MX],H[MX],C[MX]; vector<int> adj[MX]; multiset<pair<ll,ll>> dp[MX]; int par[MX]; int find(int v) { return par[v]==v?v:par[v]=find(par[v]); } void merge(int u, int v) { u=find(u),v=find(v); if(u==v) return; if(dp[u].size()>dp[v].size()) swap(u,v); for(auto [pos,val]:dp[u]) { dp[v].insert({pos,val}); } par[u]=v; dp[u].clear(); } void dfs(int v, int p) { int prv=-1; for(auto u:adj[v]) { if(u==p) continue; dfs(u,v); if(prv!=-1) merge(u,prv); prv=u; } if(prv!=-1) merge(v,prv); int pv=find(v); auto it=dp[pv].lower_bound(make_pair(H[v],0)); if(it==dp[pv].begin()) { dp[pv].insert(make_pair(H[v],C[v])); } else { it--; ll cur=C[v]; while(true) { if(cur>=it->second) { cur-=it->second; it=dp[pv].erase(it); if(it==dp[pv].begin()) break; it--; } else { auto [p,q]=*it; dp[pv].erase(it); dp[pv].insert({p,q-cur}); cur=0; break; } } dp[pv].insert(make_pair(H[v],C[v])); } } int main() { cin.tie(0); ios_base::sync_with_stdio(0); // set<int> st; // st.insert(1); // st.insert(2); // st.insert(3); // auto it=st.lower_bound(2); // it=st.erase(it); // cout<<(*it)<<'\n'; cin>>N; ll sum=0; for(int i=1;i<=N;i++) { cin>>A[i]>>H[i]>>C[i]; sum+=C[i]; } for(int i=2;i<=N;i++) { adj[A[i]].push_back(i); } for(int i=1;i<=N;i++) par[i]=i; dfs(1,0); ll ans=0; for(auto [pos,val]:dp[find(1)]) { ans+=val; } cout<<sum-ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...