제출 #926581

#제출 시각아이디문제언어결과실행 시간메모리
926581adhityamv도로 폐쇄 (APIO21_roads)C++17
0 / 100
2050 ms66252 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pii pair<ll,ll> #define fi first #define se second const ll INF=1000000000; const ll K=200000; ll seg[4*K]={}; ll lazy[4*K]={}; void Build(ll l,ll r,ll pos){ if(l==r){ seg[pos]=0; lazy[pos]=INF; return; } ll m=(l+r)/2; Build(l,m,2*pos); Build(m+1,r,2*pos+1); seg[pos]=seg[2*pos]+seg[2*pos+1]; lazy[pos]=INF; } void UpdateLazy(ll l,ll r,ll pos){ if(lazy[pos]==INF) return; seg[pos]=(r-l+1LL)*lazy[pos]; if(l!=r){ lazy[2*pos]=lazy[pos]; lazy[2*pos+1]=lazy[pos]; } lazy[pos]=INF; } void Update(ll l,ll r,ll pos,ll ql,ll qr,ll qval){ if(ql>qr) return; UpdateLazy(l,r,pos); if(ql>r || qr<l) return; if(ql<=l && qr>=r){ lazy[pos]=qval; UpdateLazy(l,r,pos); return; } ll m=(l+r)/2; Update(l,m,2*pos,ql,qr,qval); Update(m+1,r,2*pos+1,ql,qr,qval); seg[pos]=(seg[2*pos]+seg[2*pos+1]); } ll Query(ll l,ll r,ll pos, ll ql,ll qr){ if(ql>qr) return 0; UpdateLazy(l,r,pos); if(ql>r || qr<l) return 0; if(ql<=l && qr>=r){ return seg[pos]; } ll m=(l+r)/2; return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr)); } const ll N=100000; vector<pii> edges[N]; vector<ll> et; ll n,m; ll deg[N]; ll depth[N]; ll focc[N]; ll locc[N]; ll parent[N]; ll upweight[N]; void euler_tour(ll u,ll p){ parent[u]=p; focc[u]=et.size(); et.push_back(u); for(auto v:edges[u]){ if(v.fi==p) continue; depth[v.fi]=depth[u]+1; upweight[v.fi]=v.se; euler_tour(v.fi,u); et.push_back(u); } locc[u]=et.size()-1; } vector<ll> bydeg[N]; multiset<ll> allnums[N]; multiset<ll> topk[N]; multiset<ll> topk1[N]; ll dp[N]; ll dp1[N]; void dfs(ll u,ll p){ dp[u]=dp1[u]=0; for(auto v:edges[u]){ if(v.fi==p) continue; dfs(v.fi,u); allnums[u].insert(upweight[v.fi]+dp1[v.fi]-dp[v.fi]); dp[u]+=dp[v.fi]; dp1[u]+=dp[v.fi]; } auto it=allnums[u].end(); if(it!=allnums[u].begin()){ it--; topk[u].insert(*it); dp[u]+=max(*it,0LL); allnums[u].erase(it); } } ll k=2; void updatepp(){ vector<pii> needupdate; for(ll i:bydeg[k]) needupdate.push_back(mp(depth[i],i)); for(ll i:bydeg[k]){ if(i==0) continue; if(deg[parent[i]]>=k) continue; needupdate.push_back(mp(depth[parent[i]],parent[i])); } sort(needupdate.begin(),needupdate.end(),greater<pii>()); for(auto pa:needupdate){ ll u=pa.se; ll orval=dp[u]; ll orval1=dp1[u]; if(topk1[u].size()!=topk[u].size()){ dp1[u]+=max(*topk[u].begin(),0LL); topk1[u].insert(*topk[u].begin()); } if(!allnums[u].empty()){ auto it=allnums[u].end(); it--; dp[u]+=max(*it,0LL); topk[u].insert(*it); allnums[u].erase(it); } ll ex=Query(0,m-1,1,focc[u],locc[u]); dp[u]+=ex; dp1[u]+=ex; if(u==0) continue; if(deg[u]<k){ Update(0,m-1,1,focc[u],locc[u],0); Update(0,m-1,1,focc[u],focc[u],dp[u]-orval); } else{ ll p=parent[u]; ll val=upweight[u]+orval1-orval; bool w=false; bool w1=false; if(topk1[p].find(val)!=topk1[p].end()){ topk[p].erase(topk[p].find(val)); topk1[p].erase(topk1[p].find(val)); dp[p]-=max(val,0LL); dp1[p]-=max(val,0LL); } else if(topk[p].find(val)!=topk[p].end()){ topk[p].erase(topk[p].find(val)); dp[p]-=max(val,0LL); } else{ allnums[p].erase(allnums[p].find(val)); } val=upweight[u]+dp1[u]-dp[u]; topk[p].insert(val); dp[p]+=max(val,0LL); topk1[p].insert(val); dp1[p]+=max(val,0LL); if(topk[p].size()>=k){ auto it=topk[p].begin(); allnums[p].insert(*it); dp[p]-=max(*it,0LL); topk[p].erase(it); } if(topk1[p].size()>=k-1){ dp1[p]-=max(*topk1[p].begin(),0LL); topk1[p].erase(topk1[p].begin()); } } } Update(0,m-1,1,0,n-1,0); k++; } vector<ll> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){ n=nn; ll tot=0; for(ll i=0;i<n-1;i++){ edges[u[i]].push_back(mp(v[i],w[i])); edges[v[i]].push_back(mp(u[i],w[i])); deg[u[i]]++,deg[v[i]]++; tot+=w[i]; } depth[0]=0; euler_tour(0,-1); m=et.size(); vector<ll> ans; ans.push_back(tot); dfs(0,-1); ans.push_back(tot-dp[0]); for(ll i=0;i<n;i++){ for(ll j=0;j<=deg[i];j++) bydeg[j].push_back(i); } Build(0,m-1,1); while(k<n){ updatepp(); ans.push_back(tot-dp[0]); break; } return ans; }

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

roads.cpp: In function 'void updatepp()':
roads.cpp:156:30: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  156 |             if(topk[p].size()>=k){
      |                ~~~~~~~~~~~~~~^~~
roads.cpp:162:31: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  162 |             if(topk1[p].size()>=k-1){
      |                ~~~~~~~~~~~~~~~^~~~~
roads.cpp:138:18: warning: unused variable 'w' [-Wunused-variable]
  138 |             bool w=false;
      |                  ^
roads.cpp:139:18: warning: unused variable 'w1' [-Wunused-variable]
  139 |             bool w1=false;
      |                  ^~
#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...