Submission #1277180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277180		pvpro	Road Closures (APIO21_roads)	C++20	7 / 100	2131 ms	951260 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<ll>> A, B;
vector<int> W;
vector<vector<pii>> res(1e5 + 11);

int dfs(int v, int prev = -1, int w = 0) {
    res[v].clear();
    for (auto &u : graph[v]) {
        if (u.f != prev) {
            int ans = dfs(u.f, v, u.s);
            res[v].pb(mp(ans, u.f));
//            cerr << "V " << u.f << " " << u.s << endl;
//            printv(A[res.back().f]);
//            printv(B[res.back().f]);
        }
    }
    if (res[v].empty()) {
        A[v] = {w, w};
        B[v] = {w, 0};
        W[v] = w;
        return v;
    }
    sort(all(res[v]), [&](pii a, pii b) {
        return A[a.f].size() > A[b.f].size();
    });
    while (A[res[v][0].f].size() <= graph[v].size()) {
        A[res[v][0].f].pb(A[res[v][0].f].back());
    }
    while (B[res[v][0].f].size() <= graph[v].size()) {
        B[res[v][0].f].pb(B[res[v][0].f].back());
    }
    vector<vector<int>> S(graph[v].size() + 1);
    for (int j = 0; j <= graph[v].size(); ++j) {
        if (B[res[v][0].f][j] < A[res[v][0].f][j]) {
            S[j].pb(B[res[v][0].f][j] - A[res[v][0].f][j]);
        }
        B[res[v][0].f][j] = A[res[v][0].f][j];
    }
    for (int i = 1; i < res[v].size(); ++i) {
        for (int j = 0; j < A[res[v][i].f].size(); ++j) {
            if (j <= graph[v].size()) {
                A[res[v][0].f][j] += A[res[v][i].f][j];
                B[res[v][0].f][j] += A[res[v][i].f][j];
                if (B[res[v][i].f][j] < A[res[v][i].f][j]) {
                    S[j].pb(B[res[v][i].f][j] - A[res[v][i].f][j]);
                }
            } else {
                A[res[v][0].f][j] += min(A[res[v][i].f][j], B[res[v][i].f][j]);
                B[res[v][0].f][j] += min(A[res[v][i].f][j], B[res[v][i].f][j]);
            }
        }
        for (int j = A[res[v][i].f].size(); j <= graph[v].size(); ++j) {
            if (B[res[v][i].f] < A[res[v][i].f]) {
                S[j].pb(B[res[v][i].f].back() - A[res[v][i].f].back());
            }
            A[res[v][0].f][j] += A[res[v][i].f].back();
            B[res[v][0].f][j] += A[res[v][i].f].back();
        }
    }
    for (int i = 0; i <= graph[v].size(); ++i) {
        sort(all(S[i]));
        for (int j = 0; j < min(i, (int)S[i].size()); ++j) {
            A[res[v][0].f][i] += S[i][j];
        }
        for (int j = 0; j < min(i - 1, (int)S[i].size()); ++j) {
            B[res[v][0].f][i] += S[i][j];
        }
    }
    for (auto &x : A[res[v][0].f]) {
        x += w;
    }
    B[res[v][0].f][0] = A[res[v][0].f][0];
    return res[v][0].f;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> w) {
    graph.assign(N, {});
    A.assign(N, {});
    B.assign(N, {});
    W.assign(N, -1);
    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 < A[ans].size(); ++i) {
        fin[i] = min(A[ans][i], B[ans][i]);
    }
    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]));
        U[i] = i;
        V[i] = i + 1;
        W[i] = 1;
    }

    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: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22