Submission #832031

#TimeUsernameProblemLanguageResultExecution timeMemory
832031AntekbRoad Closures (APIO21_roads)C++17
26 / 100
2063 ms30608 KiB
#include<bits/stdc++.h> #include "roads.h" #define st first #define nd second #define pb push_back #define pp pop_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii > vii; void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); const int N=1e5+5; vii E[N], E2[N]; ll dp[N][2]; int par[N]; int vis[N]; vi co[N]; vector<ll> suf[N]; void dfs(int v, int k){ for(pii e:E[v]){ int u=e.st, c=e.nd; if(u!=par[v]){ par[u]=v; dfs(u, k); } } dp[v][1]=dp[v][0]=0; vector<int> V; for(pii e:E[v]){ int u=e.st, c=e.nd; if(u!=par[v]){ dp[v][0]+=dp[u][1]; V.pb(dp[u][0]+c-dp[u][1]); } } sort(all(V)); for(int j=V.size()-1; j>=int(V.size())-k+1 && j>=0 && V[j]>0; j--){ dp[v][0]+=V[j]; } dp[v][1]=dp[v][0]; if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k]; //if(i>=2)assert(2*dp[v][1][i-1]>=dp[v][1][i]+dp[v][1][i-2]); //deb(v, dp[v][0], dp[v][1], dp[v][2]); } void dfs2(int v, int k){ for(pii e:E2[v])dfs2(e.st, k); dp[v][1]=dp[v][0]=0; vector<int> V; for(pii e:E2[v]){ int u=e.st, c=e.nd; dp[v][0]+=dp[u][1]; V.pb(dp[u][0]+c-dp[u][1]); } sort(all(V)); ll s=0; ll opt=0, opt2=0; dp[v][1]=dp[v][0]; /*for(int i:V){ deb(i); } deb(" "); for(int i:suf[v]){ deb(i); }*/ if(suf[v].size()){ for(int j=0; j<=V.size(); j++){ if(j+1<k){ opt=max(opt, suf[v].end()[max(-k+1+j, -int(suf[v].size()))]+s); //deb(j, s, suf[v].end()[-k+1+j]); } if(j<k)opt2=max(opt2, suf[v].end()[max(-k+j, -int(suf[v].size()))]+s); if(j!=V.size())s+=V[j]; } } else{ for(int j=0; j<k && j<=V.size(); j++){ if(j+1<k){ opt=max(opt,s); //deb(j, s, suf[v].end()[-k+1+j]); } if(j<k)opt2=max(opt2, s); if(j!=V.size())s+=V[j]; } } opt2=max(opt, opt2); dp[v][0]+=opt; dp[v][1]+=opt2; //deb(v, dp[v][0], dp[v][1]); } std::vector<long long> minimum_closure_costs(int n, std::vector<int> uu, std::vector<int> vv,std::vector<int> ww) { ll sum=0; for(int i=0; i<n-1; i++){ E[uu[i]].eb(vv[i], ww[i]); E[vv[i]].eb(uu[i], ww[i]); sum+=ww[i]; } vector<ll> ans(n); ans[0]=sum; par[0]=-1; int K=200; for(int i=1; i<K && i<n; i++){ dfs(0, i); ans[i]=sum-dp[0][1]; } vi todo; sum=0; for(int i=0; i<n; i++){ if(E[i].size()>=K){ if(i==0 || E[par[i]].size()<K)todo.pb(i); for(auto e:E[i]){ if(E[e.st].size()>=K && e.st!=par[i]){ //deb(i, par[i], e.st); E2[i].pb(e); } if(E[e.st].size()<K || e.st!=par[i]){ sum+=e.nd; if(E[e.st].size()<K){ co[i].pb(e.nd); } } } if(co[i].size())sort(all(co[i])); suf[i].resize(co[i].size()); for(int j=int(co[i].size())-1; j>=0; j--){ suf[i][j]=co[i][j]; if(j!=co[i].size()-1){ suf[i][j]+=suf[i][j+1]; } } } } for(int i=K; i<n; i++){ ans[i]=sum; for(int v:todo){ dfs2(v, i); ans[i]-=dp[v][1]; } } return ans; }

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:32:15: warning: unused variable 'c' [-Wunused-variable]
   32 |   int u=e.st, c=e.nd;
      |               ^
roads.cpp:52:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
      |      ~~~~~~~~^~~
roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int j=0; j<=V.size(); j++){
      |               ~^~~~~~~~~~
roads.cpp:83:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   if(j!=V.size())s+=V[j];
      |      ~^~~~~~~~~~
roads.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j=0; j<k && j<=V.size(); j++){
      |                       ~^~~~~~~~~~
roads.cpp:93:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   if(j!=V.size())s+=V[j];
      |      ~^~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:122:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |   if(E[i].size()>=K){
      |      ~~~~~~~~~~~^~~
roads.cpp:123:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |    if(i==0 || E[par[i]].size()<K)todo.pb(i);
      |               ~~~~~~~~~~~~~~~~^~
roads.cpp:125:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |     if(E[e.st].size()>=K && e.st!=par[i]){
      |        ~~~~~~~~~~~~~~^~~
roads.cpp:129:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |     if(E[e.st].size()<K || e.st!=par[i]){
      |        ~~~~~~~~~~~~~~^~
roads.cpp:131:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |      if(E[e.st].size()<K){
      |         ~~~~~~~~~~~~~~^~
roads.cpp:140:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     if(j!=co[i].size()-1){
      |        ~^~~~~~~~~~~~~~~~
#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...