Submission #1277244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277244		pvpro	Road Closures (APIO21_roads)	C++20	100 / 100	365 ms	57900 KiB

roads

#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<long long>> A, B;
vector<long long> da;
vector<vector<long long>> S;
vector<int> W;
vector<vector<pii>> res(1e5 + 11);

struct Node {
    Node *l, *r;
    ll x, y, sz, sum;
    Node (ll x_) {
        x = x_;
        l = nullptr;
        r = nullptr;
        sz = 1;
        sum = x;
        y = rnd();
    }
};

ll getSz(Node *root) {
    if (root) {
        return root->sz;
    }
    return 0;
}

ll getSum(Node *root) {
    if (root) {
        return root->sum;
    }
    return 0;
}

void update(Node *root) {
    root->sum = root->x + getSum(root->l) + getSum(root->r);
    root->sz = 1 + getSz(root->l) + getSz(root->r);
}

pair<Node*, Node*> split(Node *root, ll x) {
    if (root == nullptr) {
        return mp(root, root);
    }
    if (root->x < x) {
        auto p = split(root->r, x);
        root->r = p.f;
        update(root);
        return mp(root, p.s);
    } else {
        auto p = split(root->l, x);
        root->l = p.s;
        update(root);
        return mp(p.f, root);
    }
}

pair<Node*, Node*> splitSz(Node *root, ll x) {
    if (root == nullptr) {
        return mp(root, root);
    }
    if (getSz(root->l) < x) {
        auto p = splitSz(root->r, x - getSz(root->l) - 1);
        root->r = p.f;
        update(root);
        return mp(root, p.s);
    } else {
        auto p = splitSz(root->l, x);
        root->l = p.s;
        update(root);
        return mp(p.f, root);
    }
}

Node* merge(Node *a, Node *b) {
    if (a == nullptr) {
        return b;
    }
    if (b == nullptr) {
        return a;
    }
    if (a->y > b->y) {
        a->r = merge(a->r, b);
        update(a);
        return a;
    } else {
        b->l = merge(a, b->l);
        update(b);
        return b;
    }
}

Node *add(Node *root, ll x) {
    if (x > 0) {
        x = 0;
    }
    auto p = split(root, x);
    return merge(p.f, merge(new Node(x), p.s));
}

Node *del(Node *root, ll x) {
    if (x > 0) {
        x = 0;
    }
    auto p = split(root, x);
    return merge(p.f, splitSz(p.s, 1).s);
}

ll get(Node *root, ll x) {
    auto p = splitSz(root, x);
    ll ans = getSum(p.f);
    merge(p.f, p.s);
    return ans;
}

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));
        }
    }
    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());
    }
    for (int j = 0; j <= graph[v].size(); ++j) {
        if (B[res[v][0].f][j] < A[res[v][0].f][j] + da[res[v][0].f]) {
            S[j].pb(B[res[v][0].f][j] - A[res[v][0].f][j] - da[res[v][0].f]);
        }
        B[res[v][0].f][j] = A[res[v][0].f][j] + da[res[v][0].f];
    }
    for (int j = graph[v].size() + 1; j < A[res[v][0].f].size(); ++j) {
        A[res[v][0].f][j] = min(A[res[v][0].f][j], B[res[v][0].f][j] - da[res[v][0].f]);
        B[res[v][0].f][j] = min(A[res[v][0].f][j] + da[res[v][0].f], B[res[v][0].f][j]);
    }
    vector<vector<pair<ll, ll>>> TA(graph[v].size() + 1);
    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] + da[res[v][i].f];
                B[res[v][0].f][j] += A[res[v][i].f][j] + da[res[v][i].f];
                if (B[res[v][i].f][j] < A[res[v][i].f][j] + da[res[v][i].f]) {
                    S[j].pb(B[res[v][i].f][j] - A[res[v][i].f][j] - da[res[v][i].f]);
                }
            } else {
                A[res[v][0].f][j] += min(A[res[v][i].f][j] + da[res[v][i].f], B[res[v][i].f][j]);
                B[res[v][0].f][j] += min(A[res[v][i].f][j] + da[res[v][i].f], B[res[v][i].f][j]);
            }
        }
        if (A[res[v][i].f].size() <= graph[v].size()) {
            TA[A[res[v][i].f].size()].pb(mp(A[res[v][i].f].back() + da[res[v][i].f], B[res[v][i].f].back() - A[res[v][i].f].back() - da[res[v][i].f]));
        }
    }
    Node *root = nullptr;
    ll dopX = 0;
    for (int i = 0; i <= graph[v].size(); ++i) {
        for (auto &p : TA[i]) {
            dopX += p.f;
            root = add(root, p.s);
        }
        for (auto &x : S[i]) {
            root = add(root, x);
        }
        A[res[v][0].f][i] += get(root, i) + dopX;
        B[res[v][0].f][i] += get(root, i - 1) + dopX;
        for (auto &x : S[i]) {
            root = del(root, x);
        }
        S[i].clear();
    }
    da[res[v][0].f] += w;
    B[res[v][0].f][0] = A[res[v][0].f][0] + da[res[v][0].f];
    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, {});
    da.assign(N, 0);
    W.assign(N, -1);
    S.assign(N, {});
    vector<ll> fin(N);
    if (accumulate(all(U), 0ll) == 0) {
        sort(all(w));
        for (int i = 1; i < N; ++i) {
            fin[N - i - 1] = fin[N - i] + w[i - 1];
        }
    } else {
        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);
        for (int i = 0; i < A[ans].size(); ++i) {
            fin[i] = min(A[ans][i] + da[ans], B[ans][i]);
        }
    }
    return fin;
}

#ifdef LOCAL
static void run_with_stack_size(signed (*func)(), size_t stsize) {
    char *stack, *send;
    stack = (char *)malloc(stsize);
    send = stack+stsize-16;
    send = (char *)((uintptr_t)send/16*16);
    asm volatile(
            "mov %%rsp, (%0)\n"
            "mov %0, %%rsp\n"
            :
            : "r" (send));
    func();
    asm volatile(
            "mov (%0), %%rsp\n"
            :
            : "r"   (send));
    free(stack);
}

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] = (rnd() % 1000000000) + 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;
}
signed main() {
    run_with_stack_size(Main, 1024*1024*1024);
}
#endif

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