제출 #1277154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277154		pvpro	도로 폐쇄 (APIO21_roads)	C++20	0 / 100	2112 ms	418592 KiB

roads

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ushort = unsigned short;

#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;

template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
    for (auto &x : v) {
        in >> x;
    }
    return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
    for (auto &x : v) {
        out << x << " ";
    }
    return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x -= delta;
    }
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x += delta;
    }
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<vector<pii>> graph;

vector<vector<pair<ll, ll>>> DP;
vector<pair<ll, ll>> D;
vector<int> W;

int dfs(int v, int prev = -1, int w = 0) {
    vector<int> res;
    for (auto &u : graph[v]) {
        if (u.f != prev) {
            res.pb(dfs(u.f, v, u.s));
        }
    }
    if (res.empty()) {
        DP[v] = {mp(w, w)};
        D[v] = mp(0, 0);
        W[v] = w;
        return v;
    }
    sort(all(res), [&](int &a, int &b) {
        return DP[a].size() > DP[b].size();
    });
    int pw = graph[v].size();
    vector<vector<int>> SUB(pw);
    vector<vector<int>> toAdd(pw);
    for (int i = 0; i < res.size(); ++i) {
        for (int j = 0; j < min(pw, (int)DP[res[i]].size()); ++j) {
            int x = DP[res[i]][j].f + D[res[i]].f;
            int y = DP[res[i]][j].s + D[res[i]].s;
            if (y < x) {
                SUB[j].pb(y - x);
            }
            if (i == 0) {
                DP[res[0]][j].s = DP[res[0]][j].f + D[res[0]].f;
            } else {
                DP[res[0]][j].f += DP[res[i]][j].f + D[res[i]].f;
                DP[res[0]][j].s += DP[res[i]][j].f + D[res[i]].f;
            }
        }
        if (DP[res[i]].size() < pw) {
            toAdd[DP[res[i]].size()].pb(-W[res[i]]);
        }
    }
    for (int i = 1; i < res.size(); ++i) {
        for (int j = pw; j < DP[res[i]].size(); ++j) {
            DP[res[0]][j].f += min(DP[res[i]][j].f + D[res[i]].f, DP[res[i]][j].s + D[res[i]].s);
            DP[res[0]][j].s += min(DP[res[i]][j].f + D[res[i]].f, DP[res[i]][j].s + D[res[i]].s);
        }
    }
    while (DP[res[0]].size() < pw) {
        DP[res[0]].pb(mp(-D[res[0]].f, -D[res[0]].s));
    }
    vector<ll> dop;
    ll dopX = 0;
    for (int i = 0; i < pw; ++i) {
        for (auto &x : toAdd[i]) {
            dop.pb(x);
            dopX -= x;
        }
        for (auto &x : dop) {
            SUB[i].pb(x);
        }
        sort(all(SUB[i]));
        DP[res[0]][i].s += dopX;
        for (int j = 0; j < min((int)SUB[i].size(), i - 1); ++j) {
            DP[res[0]][i].s += SUB[i][j];
        }
        DP[res[0]][i].f += dopX;
        for (int j = 0; j < min((int)SUB[i].size(), i); ++j) {
            DP[res[0]][i].f += SUB[i][j];
        }
    }
    D[res[0]].f += w;
    W[res[0]] = w;
    DP[res[0]][0].s += w;
    return res[0];
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> w) {
    graph.assign(N, {});
    DP.assign(N, {});
    W.assign(N, -1);
    D.assign(N, mp(0, 0));
    for (int i = 0; i < N - 1; ++i) {
        graph[U[i]].pb(mp(V[i], w[i]));
        graph[V[i]].pb(mp(U[i], w[i]));
    }
    auto ans = dfs(0);
    vector<ll> fin(N);
    for (int i = 0; i < DP[ans].size(); ++i) {
        fin[i] = min(DP[ans][i].f + D[ans].f, DP[ans][i].s + D[ans].s);
    }
    return fin;
}

#ifdef LOCAL
int main() {
    freopen("in.txt", "r", stdin);
    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) {
        assert(3 == scanf("%d %d %d", &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;
}
#endif

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