제출 #644416

#제출 시각아이디문제언어결과실행 시간메모리
644416czhang2718도로 폐쇄 (APIO21_roads)C++17
0 / 100
804 ms77640 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int N=1e5; int n; vector<vector<int>> adj[N]; int deg[N]; vector<vector<int>> edges; bool vis[N]; ll dp[N][2]; struct Fenwick{ int n; vector<ll> bit; Fenwick(){} void init(int n){ this->n=n; bit.resize(n+1); } void upd(int i, int v){ i++; while(i<=n){ bit[i]+=v; i+=i&-i; } } ll get_sum(int i){ i++; ll ret=0; while(i){ ret+=bit[i]; i-=i&-i; } return ret; } }; Fenwick f0[N], f1[N]; vector<int> val[N]; void dfs(int x, int k){ vis[x]=1; vector<ll> best; for(auto e:adj[x]){ int v=e[0]; if(deg[v]<k) break; if(!vis[v]){ // cout << x << "->" << v << "\n"; dfs(v, k); dp[x][0]+=dp[v][1]; dp[x][1]+=dp[v][1]; best.push_back(dp[v][0]-dp[v][1]+e[1]); } } sort(best.begin(), best.end()); vector<ll> ss=best; ss.push_back(0); for(int i=best.size()-1; i>=0; i--){ ss[i]=ss[i+1]+best[i]; } ll sum=0; int cnt; // for(int b:best) cout << b << " "; // cout << "\n"; auto check=[&](int b, int k)->bool{ int i=lower_bound(val[x].begin(), val[x].end(), b)-val[x].begin(); cnt=f0[x].get_sum(adj[x].size()-1)-f0[x].get_sum(i-1); int j=lower_bound(best.begin(), best.end(), b)-best.begin(); cnt+=best.size()-j; sum=f1[x].get_sum(adj[x].size()-1)-f1[x].get_sum(i-1)+ss[j]; return cnt>=k; }; int b=0; for(int i=30; i>=0; i--){ if(check(b+(1<<i), k)) b+=(1<<i); } check(b, k); dp[x][1]=sum-b*(cnt-k); b=0; for(int i=30; i>=0; i--){ if(check(b+(1<<i), k-1)) b+=(1<<i); } check(b, k-1); // cout << cnt << " " << k-1 << "\n"; dp[x][0]=sum-b*(cnt-(k-1)); dp[x][0]=max(dp[x][0], 0LL); dp[x][1]=max(dp[x][1], 0LL); // cout << "dp[" << x << "][1] " << dp[x][1] << "\n"; // cout << "dp[" << x << "][0] " << dp[x][0] << "\n"; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n=N; vector<ll> ret; ll E=0; for(int w:W) E+=w; for(int i=0; i<n-1; i++){ edges.push_back({U[i],V[i],W[i]}); adj[U[i]].push_back({V[i],W[i]}); adj[V[i]].push_back({U[i],W[i]}); deg[U[i]]++; deg[V[i]]++; } vector<vector<vector<int>>> ed(n); map<pair<int, int>, int> ind; for(int i=0; i<n; i++){ f0[i].init(adj[i].size()); f1[i].init(adj[i].size()); sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){ return a[1]<b[1]; }); for(int j=0; j<adj[i].size(); j++){ ind[{i, adj[i][j][0]}]=j; val[i].push_back(adj[i][j][1]); } // cout << "val " << i << "\n"; // for(int v:val[i]) cout << v << " "; // cout << "\n"; sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){ return deg[a[0]]>deg[b[0]]; }); } for(auto e:edges){ ed[min(deg[e[1]], deg[e[0]])].push_back(e); } vector<int> nodes; for(int i=0; i<n; i++) nodes.push_back(i); for(int k=0; k<n; k++){ ll ans=0; // cout << "k " << " " << k << "\n"; for(int x:nodes){ if(!vis[x]) dfs(x, k), ans+=dp[x][1]; } // cout << E-ans << "\n"; ret.push_back(E-ans); for(int x:nodes) vis[x]=0, dp[x][0]=dp[x][1]=0; for(auto e:ed[k]){ int u=e[0], v=e[1]; for(int it=0; it<2; it++, swap(u,v)){ if(deg[u]==k){ int j=ind[{v,u}]; f1[v].upd(j, val[v][j]); f0[v].upd(j, 1); } } } vector<int> nodes2; for(int x:nodes){ if(deg[x]>k) nodes2.push_back(x); } swap(nodes, nodes2); } return ret; } // int main(){ // cin.tie(0)->sync_with_stdio(0); // minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5}); // } // nobody hears me scream

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

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int j=0; j<adj[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
#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...