Submission #980668

#	Time	Username	Problem	Language	Result	Execution time	Memory
980668		vjudge1	Road Closures (APIO21_roads)	C++17	5 / 100	220 ms	60104 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

template<typename T>
struct fenwick {
    vector<T> t;

    void init(int n) {
        t.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            t[i] = 0;
        }
    }

    void upd(int x, T y) {
        while (x < t.size()) {
            t[x] += y;
            x += x & -x;
        }
    }

    T get(int x) {
        T res = 0;
        while (x > 0) {
            res += t[x];
            x -= x & -x;
        }
        return res;
    }

    int lower_bound(T k) {
        if (k == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 20; i >= 0; i--) {
            if (res + (1 << i) < t.size() && t[res + (1 << i)] < k) {
                res += (1 << i);
                k -= t[res];
            }
        }
        return res + 1;
    }
};

struct DSU {
    vector<int> p;
    vector<int> s;
    set<int> leaders;

    DSU(int n) : p(n), s(n, 1) {
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    int get(int x) {
        return p[x] == x ? x : p[x] = get(p[x]);
    }

    bool make(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        } else if (s[x] > s[y]) {
            swap(x, y);
        }
        leaders.erase(x);
        p[x] = y;
        s[y] += s[x];
        return true;
    }
};


int n;
int A[N];
int B[N];
int C[N];
vector<int> v[N];
vector<int> g[N];

fenwick<int> fc[N];
fenwick<long long> ft[N];

vector<int> to_add[N];
bool used[N];

long long f[N][2];
const long long inf = 1e18;

long long get(int x, int k) {
    if (k <= 0) {
        return 0;
    } else if (k > v[x].size() - g[x].size()) {
        return inf;
    }
    return ft[x].get(fc[x].get(k));
}

void dfs(int x, int last_i, int k) {
    for (int i: g[x]) {
        if (i == last_i) {
            continue;
        }
        int y = A[i] ^ B[i] ^ x;
        dfs(y, i, k);
    }

    for (int z = 0; z < 2; z++) {
        f[x][z] = inf;
        int to_del = v[x].size() - k - z;
        long long cur = (z == 0 ? 0 : (last_i == -1 ? 0 : C[last_i]));

        vector<long long> shit;
        for (int i: g[x]) {
            if (i == last_i) {
                continue;
            }
            int y = A[i] ^ B[i] ^ x;

            assert (f[y][1] != inf);

            if (f[y][1] < f[y][0]) {
                cur += f[y][1];
                to_del -= 1;
            } else {
                cur += f[y][0];
                shit.push_back(f[y][1] - f[y][0]);
            }
        }
        sort(shit.begin(), shit.end());

        for (int i = 0; i <= shit.size(); i++) {
            f[x][z] = min(f[x][z], cur + get(x, to_del - i));
            if (i < shit.size()) {
                cur += shit[i];
            }
        }
    }
    long long shit = (last_i == -1 ? 0 : C[last_i]);
    assert (f[x][1] <= f[x][0] + shit);
}

map<int, int> shitId[N];

std::vector<long long> minimum_closure_costs(int N_, std::vector<int> U_,
                                             std::vector<int> V_,
                                             std::vector<int> W_) {
    n = N_;
    for (int i = 0; i < n - 1; i++) {
        int x = V_[i];
        int y = U_[i];
        v[x].push_back(i);
        v[y].push_back(i);

        A[i] = x;
        B[i] = y;
        C[i] = W_[i];
    }

    for (int i = 0; i < n; i++) {
        fc[i].init(v[i].size());
        ft[i].init(v[i].size());

        sort(v[i].begin(), v[i].end(), [&](int x, int y) {
            return C[x] < C[y];
        });

        for (int j = 0; j < v[i].size(); j++) {
            fc[i].upd(j + 1, 1);
            ft[i].upd(j + 1, C[v[i][j]]);

            shitId[i][v[i][j]] = j;
        }

        to_add[v[i].size() - 1].push_back(i);
    }

    vector<long long> res(n, 0);

    DSU d(n);
    for (int i = n - 1; i >= 0; i--) {
        for (int j: to_add[i]) {
            used[j] = true;
            d.leaders.insert(j);
            for (int id: v[j]) {
                int h = A[id] ^ B[id] ^ j;
                if (used[h]) {
                    g[j].push_back(id);
                    g[h].push_back(id);
                    d.make(j, h);

                    for (int z: {j, h}) {
                        int in = shitId[z][id];
                        assert (v[z][in] == id);
                        fc[z].upd(in + 1, -1);
                        ft[z].upd(in + 1, -C[id]);
                    }
                }
            }
        }
        for (int j: d.leaders) {
            dfs(j, -1, i);
            res[i] += f[j][0];
        }
    }

    return res;
}

Compilation message (stderr)

roads.cpp: In function 'long long int get(int, int)':
roads.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     } else if (k > v[x].size() - g[x].size()) {
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for (int i = 0; i <= shit.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
roads.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             if (i < shit.size()) {
      |                 ~~^~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
roads.cpp: In instantiation of 'void fenwick<T>::upd(int, T) [with T = int]':
roads.cpp:177:31:   required from here
roads.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         while (x < t.size()) {
      |                ~~^~~~~~~~~~
roads.cpp: In instantiation of 'void fenwick<T>::upd(int, T) [with T = long long int]':
roads.cpp:178:40:   required from here
roads.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

• 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