Submission #544580

#TimeUsernameProblemLanguageResultExecution timeMemory
544580leakedWorst Reporter 4 (JOI21_worst_reporter4)C++14
0 / 100
5 ms6612 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define vec vector #define pb push_back #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) #define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef long double ld; typedef pair<int,ll> pil; template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int N=2e5+1; const ll inf=1e18; vec<int> g[N]; int c[N],a[N],h[N]; struct fenwick{ ll fnw[N]; fenwick(){ fill(fnw,fnw+N,0); } void upd(int i,ll x){ ++i; while(i<N){ fnw[i]+=x; i+=i&-i; } } ll get(int i){ ++i; ll ans=0; while(i>0){ ans+=fnw[i]; i-=i&-i; } return ans; } }fen; map<int,ll> mp; vec<pil> *dps[N]; int dp[N]; void dfs1(int v){ dp[v]=1; for(auto &z : g[v]){ dfs1(z); dp[v]+=dp[z]; } } void dfs(int v,bool keep=0){ // for(int i=0;i<N;i++){ // dp[v][i]=(h[v]==i?0:c[v]); // } // cout<<"DFS "<<v<<' '<<h[v]<<endl; int big=-1; for(auto &z : g[v]){ if(big==-1 || dp[z]>dp[big]) big=z; } for(auto &z : g[v]){ if(z==big) continue; dfs(z,0); } if(big!=-1){ dfs(big,1); dps[v]=dps[big]; } else{ dps[v]=new vec<pil>(); } for(auto &z : g[v]){ if(z==big) continue; for(auto &u : *dps[z]){ mp[u.f]+=u.s; fen.upd(u.f,u.s); } (*dps[z]).clear(); } if(h[v]!=0){ fen.upd(0,c[v]);mp[0]+=c[v]; mp[h[v]]-=c[v];fen.upd(h[v],-c[v]); }else mp[h[v]]=0; mp[h[v]+1]+=c[v];fen.upd(h[v]+1,c[v]); auto it=mp.lower_bound(h[v]); vec<pil> del; ll myval=fen.get(h[v]); while(it!=mp.begin()){ --it; if(fen.get(it->f)>=myval) del.pb(*it); else break; } // for(auto &z : mp) // cout<<"DP1 "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl; reverse(all(del)); for(auto &z : del){ ll dt=myval-fen.get(z.f); fen.upd(z.f,dt); // cout<<"CHECK "<<z.f<<' '<<fen.get(z.f)<<' '<<myval<<endl; mp[z.f]+=dt; if(mp[z.f]==0) mp.erase(z.f); } { ll dt=myval-fen.get(h[v]); fen.upd(h[v],dt); mp[h[v]]+=dt; } // for(auto &z : del) // mp.erase(z.f),fen.upd(z.f,-z.s); // for(auto &z : mp) // cout<<"DP "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl; if(!keep){ for(auto &u : mp) fen.upd(u.f,-u.s),(*dps[v]).pb(u); mp.clear(); } // f } signed main(){ fast_resp; int n; cin>>n; vec<int>kek; for(int i=0;i<n;i++){ cin>>a[i]>>h[i]>>c[i];--a[i]; if(a[i]!=i) g[a[i]].pb(i); kek.pb(h[i]); } sort(all(kek));kek.erase(unique(all(kek)),kek.end()); for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin(); dfs1(0);dfs(0); cout<<(*dps[0])[0].s; return 0; } /* 2 1 89 964898447 2 20 952129455 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...