Submission #643790

#	Time	Username	Problem	Language	Result	Execution time	Memory
643790		czhang2718	Road Closures (APIO21_roads)	C++17	0 / 100	2076 ms	58032 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;
multiset<ll> ex[N];
bool vis[N];
ll dp[N][2];

void dfs(int x, int k){
    vis[x]=1;
    vector<ll> best={-(ll)1e18};
    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> del;
    for(int i=0; i<k; i++){
        ll a=*--ex[x].end();
        ll b=best.back();
        if(a>b){
            // cout << "dp[" << x << "] use " << a << '\n';
            dp[x][1]+=a;
            if(i!=k-1) dp[x][0]+=a;
            del.push_back(a);
            ex[x].erase(--ex[x].end());
        }
        else{
            // cout << "dp[" << x << "] use " << b << '\n';
            dp[x][1]+=b;
            if(i!=k-1) dp[x][0]+=b;
            best.pop_back();
        }
    }
    for(ll a:del) ex[x].insert(a);
    dp[x][1]=max(dp[x][1], 0LL);
    // cout << "dp[" << x << "][0] = " << dp[x][0] << "\n";
    // cout << "dp[" << x << "][1] = " << dp[x][1] << "\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=accumulate(W.begin(), W.end(), 0LL);
  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);
  for(int i=0; i<n; i++){
      sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){
          return deg[a[0]]>deg[b[0]];
      });
      ex[i].insert(-1e18);
  }
  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];
          if(deg[u]==k && deg[v]==k){}
          else if(deg[u]==k) ex[v].insert(e[2]);
          else ex[u].insert(e[2]);
      }

      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

• 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