제출 #1141139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141139		byunjaewoo	Road Closures (APIO21_roads)	C++20	100 / 100	308 ms	69576 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) {
  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];
  }
  vector<pair<int, int>> in1, in2, out1, out2;
  for(auto [next, w]:adj2[curr]) {
    if(ep[next]-dp[next]<0 || s1[curr].size()<=deg[curr]-k)
      dp[curr]+=ep[next]-dp[next], in1.push_back({ep[next]-dp[next], next}), s1[curr].insert({ep[next]-dp[next], next});
    if(s1[curr].size()>deg[curr]-k && s1[curr].rbegin()->first>0)
      dp[curr]-=s1[curr].rbegin()->first, out1.push_back(*s1[curr].rbegin()), s1[curr].erase(prev(s1[curr].end()));
    if(ep[next]-dp[next]<0 || s2[curr].size()<=deg[curr]-k-1)
      ep[curr]+=ep[next]-dp[next], in2.push_back({ep[next]-dp[next], next}), s2[curr].insert({ep[next]-dp[next], next});
    if(s2[curr].size()>deg[curr]-k-1 && s2[curr].rbegin()->first>0)
      ep[curr]-=s2[curr].rbegin()->first, out2.push_back(*s2[curr].rbegin()), s2[curr].erase(prev(s2[curr].end()));
  }
  for(auto t:out1) s1[curr].insert(t);
  for(auto t:out2) s2[curr].insert(t);
  for(auto t:in1) s1[curr].erase(t);
  for(auto t:in2) s2[curr].erase(t);
  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: 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