Submission #1107677

#TimeUsernameProblemLanguageResultExecution timeMemory
1107677imarnWorst Reporter 4 (JOI21_worst_reporter4)C++14
100 / 100
299 ms112464 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vvi vector<vi> #define pp pair<ll,int> #define ub(x,i) upper_bound(all(x),i)-x.begin() using namespace std; const int mxn=2e5+5; vector<int> g[mxn]; int a[mxn],h[mxn],c[mxn]; map<int,ll>dp[mxn]; map<int,ll>res; map<int,ll>cc; int vis[mxn]{0}; bool iscyc[mxn]{0}; vector<int>cyc; void dfs1(int u){ vis[u]=1; if(vis[a[u]]==0)dfs1(a[u]); else if(vis[a[u]]==1){ int x=a[u]; while(x!=u){ iscyc[x]=1;cyc.pb(x);x=a[x]; }cyc.pb(u);iscyc[u]=1; }vis[u]=2; } void dfs2(int u,int p){ for(auto v:g[u]){ if(v==p||iscyc[v])continue; dfs2(v,u); if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]); for(auto it:dp[v])dp[u][it.f]+=it.s; }dp[u][h[u]]+=c[u]; auto it = dp[u].upper_bound(h[u]); int cur=c[u]; for(;it!=dp[u].end();){ if(cur>=it->s){cur-=it->s;auto ij=it;it++;dp[u].erase(ij);} else {it->s-=cur;break;} } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n;ll rs=0; for(int i=1;i<=n;i++){ cin>>a[i]>>h[i]>>c[i];h[i]=-h[i]; g[a[i]].pb(i);rs+=c[i]; }ll rs2=0; for(int i=1;i<=n;i++){ if(vis[i])continue; dfs1(i); for(auto it:cyc){ for(auto v:g[it]){ if(!iscyc[v])dfs2(v,it); for(auto ij:dp[v])res[ij.f]+=ij.s; }cc[h[it]]+=c[it]; } vector<pair<int,ll>>vec; for(auto it:res)vec.pb(it); sort(all(vec));for(int i=1;i<vec.size();i++)vec[i].s+=vec[i-1].s; ll rs3=0; for(auto it:cyc){ if(vec.empty()){ rs3=max(cc[h[it]],rs3);continue; } if(h[it]<vec[0].f){ rs3=max(rs3,max(cc[h[it]],vec.back().s)); continue; } auto ij = --lower_bound(all(vec),make_pair(h[it],(ll)1e16)); rs3=max(rs3,ij->s+max(cc[h[it]],vec.back().s-ij->s)); } rs2+=rs3; cyc.clear(); cc.clear(); res.clear(); }cout<<rs-rs2; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:67:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         sort(all(vec));for(int i=1;i<vec.size();i++)vec[i].s+=vec[i-1].s;
      |                                    ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...