Submission #1141133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141133		byunjaewoo	Road Closures (APIO21_roads)	C++20	21 / 100	2095 ms	71368 KiB

roads

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

const int N=100010;
int n, deg[N], par[N], pw[N];
ll dp[N], ep[N];
bool chk[N];
vector<int> v[N], c;
vector<pair<int, int>> st1[N], st2[N];
vector<pair<int, int>> adj[N], adj2[N];
ll sum1[N], sum2[N];
set<pair<int, int>> s1[N], s2[N];
vector<ll> ans;

void dfs0(int curr, int prev) {
  for(auto [next, w]:adj[curr]) if(next!=prev) par[next]=curr, pw[next]=w, st1[curr].push_back({w, next}), dfs0(next, curr);
  sort(st1[curr].rbegin(), st1[curr].rend());
  st2[curr]=st1[curr];
}

void dfs(int curr, int k, bool root=false) {
  set<pair<int, int>> tmp1=s1[curr], tmp2=s2[curr];
  dp[curr]=sum1[curr], ep[curr]=pw[curr]+sum2[curr];
  for(auto [next, w]:adj2[curr]) {
    dfs(next, k);
    dp[curr]+=dp[next], ep[curr]+=dp[next];
  }
  for(auto [next, w]:adj2[curr]) {
    if(s1[curr].size()>deg[curr]-k) {
      if(ep[next]-dp[next]<0) s1[curr].insert({ep[next]-dp[next], next}), dp[curr]+=ep[next]-dp[next];
    }
    else if(s1[curr].size()<deg[curr]-k) dp[curr]+=ep[next]-dp[next], s1[curr].insert({ep[next]-dp[next], next});
    else if(s1[curr].rbegin()->first>ep[next]-dp[next]) {
      if(s1[curr].rbegin()->first>0) dp[curr]-=s1[curr].rbegin()->first, s1[curr].erase(prev(s1[curr].end()));
      dp[curr]+=ep[next]-dp[next], s1[curr].insert({ep[next]-dp[next], next});
    }
    if(s2[curr].size()>deg[curr]-k-1) {
      if(ep[next]-dp[next]<0) s2[curr].insert({ep[next]-dp[next], next}), ep[curr]+=ep[next]-dp[next];
    }
    else if(s2[curr].size()<deg[curr]-k-1) ep[curr]+=ep[next]-dp[next], s2[curr].insert({ep[next]-dp[next], next});
    else if(!s2[curr].empty() && s2[curr].rbegin()->first>ep[next]-dp[next]) {
      if(s2[curr].rbegin()->first>0) ep[curr]-=s2[curr].rbegin()->first, s2[curr].erase(prev(s2[curr].end()));
      ep[curr]+=ep[next]-dp[next], s2[curr].insert({ep[next]-dp[next], next});
    }
    else if(ep[next]-dp[next]<0) {
      ep[curr]+=ep[next]-dp[next], s2[curr].insert({ep[next]-dp[next], next});
    }
  }
  s1[curr]=tmp1, s2[curr]=tmp2;
  if(root) {
    if(curr!=1) ans[k]+=min(dp[curr], ep[curr]);
    else ans[k]+=dp[curr];
  }
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  n=N;
  ans.resize(n);
  for(int i=0; i<n-1; i++) {
    U[i]++, V[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]]++;
  }
  for(int i=1; i<=n; i++) v[deg[i]].push_back(i);
  dfs0(1, 0);
  for(int k=n-1; k>=0; k--) {
    for(int j:v[k+1]) {
      adj2[par[j]].push_back({j, pw[j]});
      chk[j]=true, c.push_back(j);
      if(s1[par[j]].find({pw[j], j})!=s1[par[j]].end()) s1[par[j]].erase({pw[j], j}), sum1[par[j]]-=pw[j];
      if(s2[par[j]].find({pw[j], j})!=s2[par[j]].end()) s2[par[j]].erase({pw[j], j}), sum2[par[j]]-=pw[j];
    }
    for(int j:c) {
      while(s1[j].size()<deg[j]-k && !st1[j].empty()) {
        pair<int, int> tmp=st1[j].back(); st1[j].pop_back();
        if(chk[tmp.second]) continue;
        s1[j].insert(tmp), sum1[j]+=tmp.first;
      }
      while(s2[j].size()<deg[j]-k-1 && !st2[j].empty()) {
        pair<int, int> tmp=st2[j].back(); st2[j].pop_back();
        if(chk[tmp.second]) continue;
        s2[j].insert(tmp), sum2[j]+=tmp.first;
      }
    }
    for(int j:c) if(!chk[par[j]]) dfs(j, k, true);
  }
  return ans;
}

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