제출 #751863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751863		Sam_a17	도로 폐쇄 (APIO21_roads)	C++17	36 / 100	2077 ms	15752 KiB

roads

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
// const long long inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, long long>> adj[N];
long long dp[N][2];
 
void dfs(int node, int parent, int max_deg) {
  int cnt = 0;
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    dfs(i.first, node, max_deg);
    cnt++;
  }
 
  if(cnt == 0) {
    dp[node][0] = dp[node][1] = 0;
  } else {
    vector<pair<long long, long long>> diff;
    for(auto i: adj[node]) {
      if(i.first == parent) continue;
      diff.push_back({dp[i.first][1] + i.second - dp[i.first][0], i.first});
    }
    sort(all(diff));
    
 
    int curr_deg = adj[node].size();
    if(max_deg >= curr_deg) {
      long long to_add = 0; 
      for(int i = 0; i < sz(diff); i++) {
        if(diff[i].first < 0) {
          long long edge = diff[i].first - dp[diff[i].second][1];
          edge += dp[diff[i].second][0];
 
          //
          to_add += dp[diff[i].second][1] + edge;
        } else {
          to_add += dp[diff[i].second][0];
        }
      }
 
      dp[node][0] = dp[node][1] = to_add;
    } else {
      {
        int qn = curr_deg - max_deg;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];
 
            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }
 
        assert(cr >= qn);
        dp[node][0] = to_add; 
      }
 
      {
        int qn = curr_deg - max_deg - 1;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];
 
            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }
 
        if(cr >= qn) {
          dp[node][1] = to_add; 
          assert(dp[node][0] >= dp[node][1]);
          dp[node][0] = max(dp[node][0], to_add);
        }
      }
    }
  }
}
 
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  bool flag1 = true, flag2 = true;;
  for(int i = 0; i < N - 1; i++) {
    if(U[i] != 0) {
      flag1 = false;
    }
 
    if(U[i] != i || V[i] != i + 1) {
      flag2 = false;
    }
  }
 
  if(flag1) {
    sort(all(W));
    vector<long long> answ(N, 0);
    int it = 0;
    for(int i = N - 2; i >= 0; i--) {
      answ[i] = answ[i + 1] + W[it++];
    }
 
    return answ;
  }
 
  if(flag2) {
    vector<long long> answ(N, 0);
    for(auto i: W) {
      answ[0] += i;
    }
 
    vector<vector<long long>> dp(N, vector<long long> (2, 0));
    dp[0][0] = 0;
    dp[0][1] = 0;
  
    for(int i = 1; i < N; i++) {
      dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + W[i - 1];
      dp[i][1] = dp[i - 1][0];
    }
 
    answ[1] = min(dp[N - 1][0], dp[N - 1][1]);
    return answ;
  }
 
  for(int i = 0; i < N - 1; i++) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }
 
  vector<long long> answ(N, 0);
  for(auto i: W) {
    answ[0] += i;
  }
 
  for(int i = 1; i < N; i++) {
    dfs(0, -1, i);
    answ[i] = dp[0][0];
  }
 
  return answ;
}

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