제출 #980571

#제출 시각아이디문제언어결과실행 시간메모리
980571happy_nodeWorst Reporter 4 (JOI21_worst_reporter4)C++17
79 / 100
289 ms57452 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 prv=-1; for(auto u:adj[v]) { dfs(u); 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 onstk[MX],degs[MX],head[MX]; vector<int> stk; void dfs0(int v) { onstk[v]=1; stk.push_back(v); if(onstk[A[v]]==0) { dfs0(A[v]); } else if(onstk[A[v]]==1) { vector<int> cyc; for(int i=stk.size()-1;i>=0;i--) { cyc.push_back(stk[i]); if(stk[i]==A[v]) break; } sort(cyc.begin(),cyc.end(),[&](int i, int j){ return H[i]>H[j]; }); for(int i=0;i+1<cyc.size();i++) { head[cyc[i+1]]=cyc[0]; A[cyc[i]]=cyc[i+1]; } head[cyc[0]]=cyc[0]; A[cyc.back()]=cyc.back(); } stk.pop_back(); onstk[v]=2; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); 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=1;i<=N;i++) { head[i]=i; if(onstk[i]==2) continue; dfs0(i); } // for(int i=1;i<=N;i++) { // cout<<A[i]<<" -> "<<i<<'\n'; // cout<<head[A[i]]<<" "<<head[i]<<'\n'; // } for(int i=1;i<=N;i++) { if(A[i]!=i) { if(head[A[i]]!=head[i]) { adj[head[A[i]]].push_back(head[i]); degs[head[i]]+=1; } else { adj[A[i]].push_back(i); degs[i]+=1; } } } for(int i=1;i<=N;i++) par[i]=i; ll ans=0; for(int i=1;i<=N;i++) { if(degs[i]==0) { dfs(i); for(auto [pos,val]:dp[find(i)]) ans+=val; } } cout<<sum-ans<<'\n'; }

컴파일 시 표준 에러 (stderr) 메시지

worst_reporter2.cpp: In function 'void dfs0(int)':
worst_reporter2.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i=0;i+1<cyc.size();i++) {
      |               ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...