Submission #981471

#	Time	Username	Problem	Language	Result	Execution time	Memory
981471		sleepntsheep	Road Closures (APIO21_roads)	C++11	12 / 100	356 ms	53736 KiB

roads

#include <stdlib.h>
#include <time.h>
#define assert(x) if(!(x))__builtin_trap()

void push(int **eh, int *eo, int i, int j) {
    int o = eo[i]++;
    if (!o) eh[i] = (int*)malloc(sizeof**eh*2);
    else if (0 == (o&(o-1))) eh[i] = (int*)realloc(eh[i], sizeof**eh*2*o);
    eh[i][o] = j;
}

#define NN 100000
#define MM (2*NN)

#define PL (1<<22)
int L[PL], R[PL], S[PL], cur;
long long Sum[PL], K[PL];
unsigned P[PL];

int node(long long key) {
    int p = ++cur;
    Sum[p] = K[p] = key;
    L[p] = R[p] = 0;
    S[p] = 1;
    P[p] = (unsigned)rand();
    return p;
}
void pul(int v) {
    if (v) {
        S[v] = S[L[v]] + S[R[v]] + 1;
        Sum[v] = K[v] + Sum[L[v]] + Sum[R[v]];
    }
}
void merge(int *v, int l, int r) {
    if (l == 0 || r == 0) {
        *v = l ^ r;
        return;
    } else if (P[l] < P[r]) {
        merge(L+r, l, L[r]);
        *v = r;
    } else {
        merge(R+l, R[l], r);
        *v = l;
    }
    pul(*v);
}
void split(int v, int *l, int *r, long long key) {
    if (!v)
         *l = 0, *r = 0;
    else if (K[v] <= key)
        split(R[v], R+v, r, key), *l = v;
    else
        split(L[v], l, L+v, key), *r = v;
    pul(v);
}
void spliti(int v, int *l, int *r, int sz) {
    if (!v)
         *l = 0, *r = 0;
    else if (S[L[v]] < sz)
        split(R[v], R+v, r, sz - 1 - S[L[v]]), *l = v;
    else
        split(L[v], l, L+v, sz), *r = v;
}
void add(int *v, long long key)
{
    int t1, t2, t3, t4;
    split(*v, &t2, &t3, key);
    split(t2, &t1, &t2, key - 1);
    merge(&t2, t2, node(key));
    merge(&t4, t1, t2);
    merge(v, t4, t3);
}
void remove(int *v, long long key) {
    int t1, t2, t3, t4, t5;
    split(*v, &t2, &t3, key);
    split(t2, &t1, &t2, key - 1);
    spliti(t2, &t4, &t5, 1);
    merge(&t1, t1, t5);
    merge(v, t1, t3);
}
long long min_k_sum(int v, int k) {
    if (!v || !k)
        return 0;
    if (S[L[v]] >= k)
        return min_k_sum(L[v], k);
    return K[v] + Sum[L[v]] + min_k_sum(R[v], k - 1 - S[L[v]]);
}

#include "roads.h"
#include <vector>

long long dp_loose[NN], dp_tight[NN], delsum[NN];
int deg[NN], *eh[NN], eo[NN], heap[NN], time_visited[NN];

#include<set>
#include<utility>

std::set<std::pair<int, int> > gg[NN];

void forest_remove(int i) {
    for (auto [w, j] : gg[i]) {
        delsum[j] += w;
        add(heap + j, -w);
        gg[j].erase(std::make_pair(w, i));
    }
}

void dfs(int u, int p, int k) {
    long long base;

    time_visited[u] = k;
    for (auto [w, v] : gg[u])
        if (v != p)
            dfs(v, u, k);

    base = delsum[u];

    for (auto [w, v] : gg[u]) if (v != p) {
        base += w + dp_tight[v];
        long long xx = dp_loose[v] - w - dp_tight[v];
        if (xx <= 0)
            add(heap + u, xx);
    }

    dp_tight[u] = base + min_k_sum(heap[u], k);
    dp_loose[u] = base + min_k_sum(heap[u], k - 1);

    for (auto [w, v] : gg[u]) {
        long long xx = dp_loose[v] - w - dp_tight[v];
        if (xx <= 0)
            remove(heap + u, xx);
    }
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    srand(time(0));
    int i, k, ii;
    std::vector<long long> ans(N);

    for (i = 0; i < N - 1; ++i) {
        ++deg[U[i]], ++deg[V[i]];
        gg[U[i]].emplace(W[i], V[i]);
        gg[V[i]].emplace(W[i], U[i]);
    }

    std::set<int> interesting;
    for (i = 0; i < N; ++i) {
        time_visited[i] = -1;
        push(eh, eo, deg[i], i);
        interesting.insert(i);
    }

    for (k = 0; k < N; ++k) {
        for (ii = 0; ii < eo[k]; ++ii) {
            forest_remove(eh[k][ii]);
            interesting.erase(eh[k][ii]);
        }
        free(eh[k]);

        for (auto ii : interesting)
            if (time_visited[ii] != k) {
                dfs(ii, -1, k);
                ans[k] += dp_tight[ii];
            }
    }

    return ans;
}

/*
 * sum deg(v) = 2m = 2n-2
 *
 * let f(x) = count of vertices with degree >= x
 *
 * Lemma:
 *  sum f(x) for all x in [0..n-1] = sum deg(v) = 2m
 *
 * Proof:
 *  - Contribution of node u to sum f(x) is deg(u)
 *
 *  for each edge (u, v), degree u and v increases by one
 *  subsequently, each edge contribute two to sum f(x)
 *
 *
 *
 * N = 100000:
 *  sort vertices by deg
 *
 *  maintain induced subgraph of vertices with deg >= k for each k
 *  do dp on the forest, need to maintain heap of edges connecting node going outside the forest too
 */

Compilation message (stderr)

roads.cpp: In function 'void forest_remove(int)':
roads.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [w, j] : gg[i]) {
      |               ^
roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:112:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |     for (auto [w, v] : gg[u])
      |               ^
roads.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for (auto [w, v] : gg[u]) if (v != p) {
      |               ^
roads.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for (auto [w, v] : gg[u]) {
      |               ^

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