Submission #412808

#	Time	Username	Problem	Language	Result	Execution time	Memory
412808		two_sides	Road Closures (APIO21_roads)	C++17	7 / 100	182 ms	50896 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}

const long long INF = 1e18;
const int MAXN = 200005;

struct Fenwick {
    vector <int> cnt; int N, LOG;
    vector <long long> sum;

    void init(int N) {
        this->N = N;
        cnt.resize(N + 1);
        sum.resize(N + 1);
        LOG = __lg(N);
    }

    void add(int i, int v) {
        for (; i <= N; i += i & -i) {
            cnt[i]++; sum[i] += v;
        }
    }

    long long get(int k) {
        if (k < 0) return 0;
        int p = 0; long long ans = 0;
        for (int l = 1 << LOG; l > 0; l >>= 1)
            if (p + l <= N && k >= cnt[p + l]) {
                k -= cnt[p += l]; ans += sum[p];
            }
        return k > 0 ? INF : ans;
    }
};

int par[MAXN], val[MAXN], ord[MAXN];
vector <pair <int, int>> adj[MAXN];
long long DP[MAXN][2];
int prv[MAXN], nxt[MAXN], ptr, lim;
int tin[MAXN], tout[MAXN], ver[MAXN];
Fenwick BIT[MAXN];

void del(int i) {
    nxt[prv[i]] = nxt[i];
    prv[nxt[i]] = prv[i];
}

void DFS1(int u) {
    ver[tin[u] = ++ptr] = u;
    int cnt = 0;
    for (auto e : adj[u]) {
        int v, w; tie(w, v) = e;
        if (v != par[u]) {
            par[v] = u; val[v] = w;
            ord[v] = ++cnt; DFS1(v);
        }
    }
    tout[u] = ptr;
}

void DFS2(int u) {
    vector <long long> tmp;
    long long sum = 0;
    while (nxt[ptr] <= tout[u]) {
        ptr = nxt[ptr];
        int v = ver[ptr]; DFS2(v);
        if (par[v] == u) {
            sum += DP[v][0];
            tmp.push_back(DP[v][1] - DP[v][0]);
        } else sum += min(DP[v][1], DP[v][0]);
    }
    int can = adj[u].size() - lim;
    DP[u][0] = min(INF, sum + BIT[u].get(can));
    DP[u][1] = min(INF, sum + BIT[u].get(can - 1));
    for (int i = 0; i < tmp.size(); i++) {
        sum += tmp[i];
        cmin(DP[u][0], sum + BIT[u].get(can - i - 1));
        cmin(DP[u][1], sum + BIT[u].get(can - i - 2));
    }
    if (u) DP[u][1] = DP[u][1] + val[u];
    else DP[u][1] = INF;
}

long long compute() {
    ptr = 0; long long ans = 0;
    if (lim == 1) cerr << nxt[1] << '\n';
    while (nxt[ptr] <= tout[0]) {
        ptr = nxt[ptr];
        int u = ver[ptr]; DFS2(u);
        ans += min(DP[u][0], DP[u][1]);
    }
    return ans;
}

vector <long long> minimum_closure_costs(int N,
vector <int> U, vector <int> V, vector <int> W) {
    vector <int> nodes;
    for (int i = 0; i < N; i++) {
        adj[i].clear();
        prv[i + 1] = i; nxt[i + 1] = i + 2;
        nodes.push_back(i);
    }
    prv[N + 1] = N; nxt[0] = 1;
    for (int i = 0; i + 1 < N; i++) {
        adj[U[i]].emplace_back(W[i], V[i]);
        adj[V[i]].emplace_back(W[i], U[i]);
    }
    for (int i = 0; i < N; i++) {
       BIT[i].init(adj[i].size());
       sort(adj[i].begin(), adj[i].end());
    }
    DFS1(ptr = 0);
    sort(nodes.begin(), nodes.end(),
    [&](int u, int v) {
        return adj[u].size() < adj[v].size();
    });
    vector <long long> costs(N);
    for  (int i = 0, j = 0; i < N; i++) {
        while (j < N && adj[nodes[j]].size() <= i) {
            int u = nodes[j++];
            if (u && adj[par[u]].size() > i)
                BIT[par[u]].add(ord[u], val[u]);
            del(tin[u]);
        }
        lim = i; costs[i] = compute();
    }
    return costs;
}

Compilation message (stderr)

roads.cpp: In function 'void DFS2(int)':
roads.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < tmp.size(); i++) {
      |                     ~~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:125:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |         while (j < N && adj[nodes[j]].size() <= i) {
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~
roads.cpp:127:41: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |             if (u && adj[par[u]].size() > i)
      |                      ~~~~~~~~~~~~~~~~~~~^~~

• 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