Submission #981543

#	Time	Username	Problem	Language	Result	Execution time	Memory
981543		sleepntsheep	Road Closures (APIO21_roads)	C++14	5 / 100	244 ms	52288 KiB

roads

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

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

#include "roads.h"
#include <numeric>
#include <vector>
#include<set>
#include<utility>

long long dp_loose[NN], dp_tight[NN];
int deg[NN], time_visited[NN];

std::set<int> interesting;

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

struct fenwick
{
    std::vector<long long> t;
    std::vector<int> t2;
    void init(int n) { t.assign(n, 0ll); t2.assign(n, 0); }
    void add(int p, long long k) {
        for (; p < (int)t.size(); p |= p + 1)
            t[p] += k, t2[p] += k;
    }
    long long query(int p) {
        long long z{};
        p = std::min(p, (int)t.size());
        for (; p > 0; p &= p - 1) z += t[p - 1];
        return z;
    }
    long long query2(int p) {
        if (p <= 0) return p == 0 ? 0 : 1e18;
        long long z {};
        int pos = 0, j = 1 << 20, y = 0;
        for (; j >>= 1; )
            if (pos + j <= (int)t.size() && y + t2[j + pos - 1] <= p)
                pos += j, z += t[pos-1], y += t2[pos-1];
        return z;
    }
};

fenwick ft[NN];
void forest_remove(int i) {
    interesting.erase(i);
    for (auto [w, j] : gg[i]) {
        if (deg[j] <= deg[i])
            continue;

        auto ii = std::lower_bound(gv[j].begin(), gv[j].end(), std::make_pair(w, i)) - gv[j].begin();
        ii = (int)gv[j].size() - 1 - ii;
        ft[j].add(ii, -w);
        gg[j].erase(std::make_pair(w, i));
    }
}


void dfs(int u, int p, int k) {
    long long base = -ft[u].query(1000000);

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

    std::vector<long long> vv;
    for (auto [w, v] : gg[u]) if (v != p) {
        base += w + dp_tight[v];
        long long xx = dp_loose[v] - w - dp_tight[v];
        vv.push_back(xx);
    }

    std::sort(vv.begin(), vv.end());

    dp_tight[u] = dp_loose[u] = base;

    long long run {};
    for (int i = 0; i <= std::min(k, (int)vv.size()); ++i)
    {
        dp_tight[u] = std::min(dp_tight[u], base + run + ft[u].query(k - i));
        dp_loose[u] = std::min(dp_loose[u], base + run + ft[u].query(k - 1 - i));
        if (i < (int)vv.size())
            run += vv[i];
    }
}

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

    for (int 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]);
    }
    for (int i = 0; i < N; ++i)
        for (auto xx : gg[i])
            gv[i].push_back(xx);

    std::vector<std::basic_string<int> > eh(N);

    for (int i = 0; i < N; ++i) {
        ft[i].init(deg[i]);
        time_visited[i] = -1;
        eh[deg[i]].push_back(i);
        interesting.insert(i);
    }

    for (int k = 0; k < N; ++k) {
        for (auto ii : eh[k])
            forest_remove(ii);

        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:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto [w, j] : gg[i]) {
      |               ^
roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [w, v] : gg[u]) if (v != p)
      |               ^
roads.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [w, v] : gg[u]) if (v != p) {
      |               ^

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