Submission #1003583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003583		AdamGS	Road Closures (APIO21_roads)	C++17	100 / 100	256 ms	78024 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>G[LIM], V[LIM];
vector<ll>W, S[LIM];
multiset<ll>U[LIM], NU[LIM];
ll dp[LIM][2], odw[LIM], wla[LIM], sumu[LIM], sumw, n;
void DFS(int x, int o, int k) {
  odw[x]=1;
  ll sum0=0;
  vector<ll>D;
  for(auto i : V[x]) if(i.st!=o) {
    DFS(i.st, x, k);
    sum0+=dp[i.st][0];
    D.pb(dp[i.st][1]-dp[i.st][0]);
  }
  sort(all(D));
  reverse(all(D));
  int d=min(k, (int)V[x].size())+1;
  while(D.size()<d-1) D.pb(-INF);
  vector<ll>potem;
  vector<ll>X(d+1);
  rep(i, d+1) {
    while(U[x].size()>0 && U[x].size()>k-i) {
      auto it=U[x].begin();
      auto a=*it;
      U[x].erase(it);
      potem.pb(a);
      sumu[x]-=a;
    }
    X[i]=sumu[x];
  }
  for(auto i : potem) {
    U[x].insert(i);
    sumu[x]+=i;
  }
  vector<ll>P(d);
  P[0]=sum0;
  rep(i, d-1) P[i+1]=P[i]+D[i];
  rep(i, d) if(i<k) dp[x][1]=max(dp[x][1], P[i]+X[i+1]);
  rep(i, d) dp[x][0]=max(dp[x][0], P[i]+X[i]);
  for(auto i : V[x]) if(i.st==o) dp[x][1]+=i.nd;
}
ll licz(ll k) {
  for(auto i : S[k]) {
    wla[i]=1;
    W.pb(i);
    for(auto j : G[i]) {
      if(wla[j.st]) {
        V[i].pb(j);
        V[j.st].pb({i, j.nd});
        if(NU[j.st].find(j.nd)!=NU[j.st].end()) NU[j.st].erase(NU[j.st].find(j.nd));
        else {
          U[j.st].erase(U[j.st].find(j.nd));
          sumu[j.st]-=j.nd;
        }
      } else {
        NU[i].insert(j.nd);
        sumw+=j.nd;
      }
    }
  }
  for(auto i : W) {
    odw[i]=0;
    dp[i][0]=dp[i][1]=-INF;
    while(U[i].size()>k) {
      auto it=U[i].begin();
      auto a=*it;
      sumu[i]-=a;
      U[i].erase(it);
      NU[i].insert(a);
    }
    while(U[i].size()<k && NU[i].size()>0) {
      auto it=NU[i].end(); --it;
      auto a=*it;
      sumu[i]+=a;
      U[i].insert(a);
      NU[i].erase(it);
    }
  }
  ll ans=0;
  for(auto i : W) if(!odw[i]) {
    DFS(i, i, k);
    ans+=dp[i][0];
  }
  return ans;
}
vector<ll>minimum_closure_costs(int _n, vector<int>_U, vector<int>_V, vector<int>_W) {
  n=_n;
  rep(i, n-1) {
    G[_U[i]].pb({_V[i], _W[i]});
    G[_V[i]].pb({_U[i], _W[i]});
  }
  rep(i, n) S[G[i].size()].pb(i);
  vector<ll>wynik(n);
  for(int i=n-1; i>=0; --i) {
    ll x=licz(i);
    wynik[i]=sumw-x;
  }
  return wynik;
}

Compilation message (stderr)

roads.cpp: In function 'void DFS(int, int, int)':
roads.cpp:28:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   while(D.size()<d-1) D.pb(-INF);
      |         ~~~~~~~~^~~~
roads.cpp:32:39: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |     while(U[x].size()>0 && U[x].size()>k-i) {
      |                            ~~~~~~~~~~~^~~~
roads.cpp: In function 'll licz(ll)':
roads.cpp:74:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   74 |     while(U[i].size()>k) {
      |           ~~~~~~~~~~~^~
roads.cpp:81:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   81 |     while(U[i].size()<k && NU[i].size()>0) {
      |           ~~~~~~~~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22