제출 #1033847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033847		mispertion	도로 폐쇄 (APIO21_roads)	C++17	24 / 100	2087 ms	34668 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;

ll dp[N][2];
int n, k;
vector<pair<ll, ll>> g[N];

void dfs(int v, int p, int w){
    dp[v][0] = dp[v][1] = 0;
    for(auto u : g[v])
        if(u.F != p)
            dfs(u.F, v, u.S);
    vector<pair<ll, pll>> vs = {};
    for(auto u : g[v]){
        if(u.F != p){
            vs.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}});
        }
    }
    sort(all(vs));
    reverse(all(vs));
    for(int i = 0; i < min(k, sz(vs)); i++){
        if(vs[i].F > 0){
            dp[v][0] += vs[i].S.F;
        }else{
            dp[v][0] += vs[i].S.S;
        }
    }
    for(int i = min(k, sz(vs)); i < sz(vs); i++){
        dp[v][0] += vs[i].S.S;
    }

    for(int i = 0; i < min(k - 1, sz(vs)); i++){
        if(vs[i].F > 0){
            dp[v][1] += vs[i].S.F;
        }else{
            dp[v][1] += vs[i].S.S;
        }
    }
    for(int i = min(k - 1, sz(vs)); i < sz(vs); i++){
        dp[v][1] += vs[i].S.S;
    }
    dp[v][1] += w;
}

vector<long long> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W) {
    n = _n;
    vector<ll> ans(n, 0);
    for(int i = 0; i < n - 1; i++){
        U[i]++;
        V[i]++;
        g[V[i]].pb({U[i], W[i]});
        g[U[i]].pb({V[i], W[i]});
        ans[0] += W[i];
    }
    k = 1;
    for(; k < n; k++){
        dfs(1, -1, 0);
        ans[k] = ans[0] - dp[1][0];
    }
    return ans;
}


/*int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    std::cin >> U[i] >> V[i] >> W[i];
  }
  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld",closure_costs[i]);
  }
  printf("\n");
  return 0;
}*/

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