제출 #926579

#제출 시각아이디문제언어결과실행 시간메모리
926579adhityamv도로 폐쇄 (APIO21_roads)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define mp make_pair #define pii pair<int,int> #define fi first #define se second #define setit _Rb_tree_const_iterator<long long> const int INF=1000000000; const int K=200000; int seg[4*K]={}; int lazy[4*K]={}; void Build(int l,int r,int pos){ if(l==r){ seg[pos]=0; lazy[pos]=INF; return; } int 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(int l,int r,int 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(int l,int r,int pos,int ql,int qr,int 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; } int 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]); } int Query(int l,int r,int pos, int ql,int 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]; } int m=(l+r)/2; return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr)); } const int N=100000; vector<pii> edges[N]; vector<int> et; int n,m; int deg[N]; int depth[N]; int focc[N]; int locc[N]; int parent[N]; int upweight[N]; void euler_tour(int u,int 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<int> bydeg[N]; multiset<int> allnums[N]; multiset<int> topk[N]; multiset<int> topk1[N]; int dp[N]; int dp1[N]; void dfs(int u,int 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); } } int k=2; void updatepp(){ vector<pii> needupdate; for(int i:bydeg[k]) needupdate.push_back(mp(depth[i],i)); for(int 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){ int u=pa.se; int orval=dp[u]; int 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); } int 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{ int p=parent[u]; int 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<int> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){ n=nn; int tot=0; for(int 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<int> ans; ans.push_back(tot); dfs(0,-1); ans.push_back(tot-dp[0]); for(int i=0;i<n;i++){ for(int 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]); } return ans; }

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

roads.cpp: In function 'void updatepp()':
roads.cpp:157: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]
  157 |             if(topk[p].size()>=k){
      |                ~~~~~~~~~~~~~~^~~
roads.cpp:163: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]
  163 |             if(topk1[p].size()>=k-1){
      |                ~~~~~~~~~~~~~~~^~~~~
roads.cpp:139:18: warning: unused variable 'w' [-Wunused-variable]
  139 |             bool w=false;
      |                  ^
roads.cpp:140:18: warning: unused variable 'w1' [-Wunused-variable]
  140 |             bool w1=false;
      |                  ^~
/usr/bin/ld: /tmp/ccpcASLj.o: in function `main':
grader.cpp:(.text.startup+0x277): undefined reference to `minimum_closure_costs(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status