제출 #1112140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112140		abczz	도로 폐쇄 (APIO21_roads)	C++17	31 / 100	2056 ms	35056 KiB

roads

#include "roads.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long

using namespace std;

bool visited[100000], B[100000];
ll f, z, dp[100000][2];
vector <ll> deg[100000];
vector <ll> X, F;
vector <array<ll, 2>> adj[100000];

void dfs(ll u, ll p) {
  visited[u] = 1;
  priority_queue <ll, vector <ll>, greater<ll> > pq;
  ll res = 0;
  for (auto [v, w] : adj[u]) {
    if (v == p) continue;
    if (B[v]) dfs(v, u);
    else dp[v][0] = dp[v][1] = 0;
    res += dp[v][1] + w;
    pq.push(dp[v][0] - dp[v][1] - w);
  }
  for (int i=0; i<z-1; ++i) {
    if (pq.empty()) break;
    auto x = pq.top();
    pq.pop();
    if (x >= 0) break;
    res += x;
  }
  dp[u][0] = res;
  if (z && !pq.empty()) {
    ll x = pq.top();
    if (x < 0) res += x;
  }
  dp[u][1] = res;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  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]});
  }
  for (int i=0; i<N; ++i) {
    deg[adj[i].size()-1].push_back(i);
  }
  for (int i=N-1; i>=0; --i) {
    z = i, f = 0;
    for (auto u : deg[i]) {
      B[u] = 1;
      X.push_back(u);
    }
    for (auto u : X) visited[u] = 0;
    for (auto u : X) {
      if (!visited[u]) {
        dfs(u, -1);
        f += dp[u][1];
      }
    }
    F.push_back(f);
  }
  reverse(F.begin(), F.end());
  return F;
}

• Subtask 1: 0 / 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