Submission #644416

#	Time	Username	Problem	Language	Result	Execution time	Memory
644416		czhang2718	Road Closures (APIO21_roads)	C++17	0 / 100	804 ms	77640 KiB

roads

#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

Compilation message (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++){
      |                  ~^~~~~~~~~~~~~~

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