Submission #561815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
561815	2022-05-13T15:29:40 Z	Cyanmond	Toll (APIO13_toll)	C++17	Compilation error	0 ms	0 KB

toll

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr i64 inf = 1ll << 60;

#define rep(i, n) for (int i = 0; i < (n); ++i)

template <typename t> void chmax(t &a, const t b) {
    if (a < b) a = b;
}

template <typename t> void chmin(t &a, const t b) {
    if (a > b) a = b;
}

struct unionfind {
    int n;
    vector<int> data;
    unionfind(const int n_) : n(n_), data(n, -1) {}
    int find(int v) {
        if (data[v] < 0)
            return v;
        else
            return data[v] = find(data[v]);
    }
    int is_same(int a, int b) { return find(a) == find(b); }
    int size(int v) { return -data[find(v)]; }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size(a) < size(b)) swap(a, b);
        data[a] += data[b];
        data[b] = a;
    }
};

struct merger {
    int n;
    vector<int> roots;
    vector<vector<int>> vals;
    merger(const int n_) {
        n = n_;
        roots.assign(n, -1);
        rep(i, n) vals.push_back({i});
    }
    int find(int a) {
        if (roots[a] < 0)
            return a;
        else
            return roots[a] = find(roots[a]);
    }
    int size(int v) { return -roots[find(v)]; }
    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size(a) < size(b)) swap(a, b);
        for (const int e : vals[b]) vals[a].push_back(e);
        roots[a] += roots[b];
        roots[b] = a;
    }
};

struct edge {
    i64 cost;
    int a;
    int b;
};

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<edge> e(m);
    rep(i, m) {
        cin >> e[i].a >> e[i].b >> e[i].cost;
        --e[i].a, --e[i].b;
    }
    vector<pair<int, int>> a(k);
    for (auto &[x, y] : a) {
        cin >> x >> y;
        --x, --y;
    }
    vector<i64> p(n);
    for (auto &e : p) cin >> e;
    sort(e.begin(), e.end(), [](edge a, edge b) { return a.cost < b.cost; });

    {
        unionfind uft(n);
        rep(i, k) uft.unite(a[i].first, a[i].second);
        merger mt(n);
        for (const auto &[cost, a, b] : e) {
            if (uft.is_same(a, b)) continue;
            uft.unite(a, b);
            mt.merge(a, b);
        }

        vector<bool> used(n);
        vector<vector<int>> groups;
        rep(i, n) {
            if (used[mt.find(i)]) continue;
            used[mt.find(i)] = true;
            groups.push_back(mt.vals[mt.find(i)]);
        }
        const int l = (int)size(groups);

        for (auto &g : groups) sort(g.begin(), g.end());
        sort(groups.begin(), groups.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        vector<int> att(n);
        rep(i, l) {
            const auto &g = groups[i];
            for (const int e : g) att[e] = i;
        }
        vector<i64> np(l);
        rep(i, n) np[att[i]] += p[i];
        p = move(np);
        for (auto &[x, y] : a) {
            x = att[x];
            y = att[y];
        }
        rep(i, m) {
            e[i].a = att[e[i].a];
            e[i].b = att[e[i].b];
        }
        vector<edge> e2;
        for (const auto &[cost, a, b] : e)
            if (a != b) e2.push_back({cost, a, b});
        e = e2;
        e2.clear();

        uft = unionfind(l);
        for (const auto &[cost, a, b] : e) {
            if (uft.is_same(a, b)) continue;
            uft.unite(a, b);
            e2.push_back({cost, a, b});
        }
        e = move(e2);
        n = l;
        m = (int)size(e);
    }

    i64 ans = 0;
    unionfind uftb(n);
    vector<vector<pair<int, int>>> tree(n);
    vector<i64> nec(n);
    rep(bit, 1 << k) {
        rep(i, n) tree[i].clear();
        auto uft = uftb;
        fill(nec.begin(),nec.end(),inf);
        bool possible = true;
        rep(i, k) {
            if (bit & (1 << i)) {
                if (uft.is_same(a[i].first, a[i].second)) {
                    possible = false;
                    break;
                }
                uft.unite(a[i].first, a[i].second);
                tree[a[i].first].emplace_back(a[i].second, i);
                tree[a[i].second].emplace_back(a[i].first, i);
            }
        }
        if (not possible) continue;
        rep(i, m) {
            if (uft.is_same(e[i].a, e[i].b)) {
                auto dfs = [&](auto &&self, const int v, const int p) -> bool {
                    for (auto &[t, c] : tree[v]) {
                        if (t == p) continue;
                        if (t == e[i].b) {
                            chmin(nec[c], e[i].cost);
                            return true;
                        }
                        if (self(self, t, v)) {
                            chmin(nec[c], e[i].cost);
                            return true;
                        }
                    }
                    return false;
                };
                assert(dfs(dfs, e[i].a, -1));
            } else {
                uft.unite(e[i].a, e[i].b);
                tree[e[i].a].emplace_back(e[i].b, -1);
                tree[e[i].b].emplace_back(e[i].a, -1);
            }
        }

        i64 res = 0;
        auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
            i64 sum = 0;
            for (const auto &[t, c] : tree[v]) {
                if (t == p) continue;
                const i64 e = self(self, t, v);
                if (c != -1) res += nec[c] * e;
                sum += e;
            }
            return sum + p[v];
        };
        dfs(dfs, 0, -1);
        chmax(ans, res);
    }

    cout << ans << endl;
}

Compilation message

toll.cpp: In lambda function:
toll.cpp:201:27: error: invalid types 'const int[const int]' for array subscript
  201 |             return sum + p[v];
      |                           ^