Submission #1197326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197326		hengliao	Road Closures (APIO21_roads)	C++20	100 / 100	1629 ms	34904 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
  const ll mxN=1e5+5;
  const ll B=150;

  vector<pll> adj[mxN];
  vector<pll> adj2[mxN];
  vll v[mxN];
  vll pre[mxN];
  vll big;
  bool pus[mxN];
  bool visited[mxN];
  ll n;
  ll dp[mxN][2];
  ll k;

  void dfs(ll cur, ll par){
    ll dumb=0;
    vll tep;
    for(auto &[chd, w]:adj[cur]){
      if(chd==par) continue;
      dfs(chd, cur);
      dumb+=dp[chd][1];
      if(dp[chd][0]-dp[chd][1]+w>0) tep.pb(dp[chd][0]-dp[chd][1]+w);
    }
    sort(tep.begin(), tep.end(), greater<ll>());
    dp[cur][0]=dumb;
    for(ll i=0;i<k-1 && i<(ll) tep.size();i++){
      dp[cur][0]+=tep[i];
    }
    dp[cur][1]=dumb;
    for(ll i=0;i<k && i<(ll) tep.size();i++){
      dp[cur][1]+=tep[i];
    }
  }

  void dfs2(ll cur, ll par){
    visited[cur]=1;
    ll dumb=0;
    vll tep;
    for(auto &[chd, w]:adj2[cur]){
      if(chd==par) continue;
      dfs2(chd, cur);
      dumb+=dp[chd][1];
      if(dp[chd][0]-dp[chd][1]+w>0) tep.pb(dp[chd][0]-dp[chd][1]+w);
    }
    sort(tep.begin(), tep.end(), greater<ll>());
    dp[cur][0]=dumb;
    ll len=k-1;
    for(ll i=0;i<k-1 && i<(ll) tep.size();i++){
      if(len-1>=(ll) v[cur].size() || tep[i]>v[cur][len-1]){
        dp[cur][0]+=tep[i];
        len--;
      }
      else{
        break;
      }
    }
    dp[cur][0]+=pre[cur][min(len, (ll) pre[cur].size()-1)];
    dp[cur][1]=dumb;
    len=k;
    for(ll i=0;i<k && i<(ll) tep.size();i++){
      if(len-1>=(ll) v[cur].size() || tep[i]>v[cur][len-1]){
        dp[cur][1]+=tep[i];
        len--;
      }
      else{
        break;
      }
    }
    dp[cur][1]+=pre[cur][min(len, (ll) pre[cur].size()-1)];
  }
}



vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  memset(pus, 0, sizeof(pus));
  n=N;
  ll sum=0;
  for(ll i=0;i<n-1;i++){
    adj[U[i]].pb({V[i], W[i]});
    adj[V[i]].pb({U[i], W[i]});
    sum+=W[i];
  }
  vll ans(n);
  for(ll i=0;i<n && i<=B;i++){
    k=i;
    dfs(0, -1);
    ans[i]=sum-dp[0][1];
  }
  for(ll i=0;i<n;i++){
    if((ll) adj[i].size()<=B){
      pus[i]=0;
    }
    else{
      pus[i]=1;
      big.pb(i);
    }
  }
  ll sum2=0;
  for(ll i=0;i<n-1;i++){
    if(!pus[U[i]] && !pus[V[i]]){
      sum2+=W[i];
    }
    else if(!pus[U[i]]){
      v[V[i]].pb(W[i]);
    }
    else if(!pus[V[i]]){
      v[U[i]].pb(W[i]);
    }
    else{
      adj2[U[i]].pb({V[i], W[i]});
      adj2[V[i]].pb({U[i], W[i]});
    }
  }
  for(ll i=0;i<n;i++){
    sort(v[i].begin(), v[i].end(), greater<ll>());
    ll p=0;
    pre[i].pb(p);
    for(auto &it:v[i]){
      p+=it;
      pre[i].pb(p);
    }
  }
  for(ll i=B+1;i<n;i++){
    k=i;
    ans[i]=sum2;
    for(auto &it:big){
      visited[it]=0;
    }
    for(auto &it:big){
      if(!visited[it]){
        dfs2(it, -1);
        ans[i]+=dp[it][1];
      }
    }
    ans[i]=sum-ans[i];
  }

  return ans;
}

• 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