Submission #1188813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188813		juliany2	Toll (APIO13_toll)	C++20	16 / 100	1 ms	3140 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

struct DSU {
    vector<int> e;
    DSU(int sz) { e = vector<int>(sz + 1, -1); }

    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same_set(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

const int N = 1e5 + 7, K = 22;
int n, m, k;
int dsu[N];
vector<int> match[N];
array<int, 2> f[N];
int p[N], head[N];
ll sz[K];
vector<array<int, 2>> adj[K];

struct DSU2 {
    vector<int> dsu;
    vector<vector<int>> match;
    vector<int> cost;

    DSU2(int n) {
        dsu = vector<int> (n + 1);
        iota(all(dsu), 0);

        match = vector<vector<int>> (n + 1);
    }

    void add(int a, int b, int i) {
        match[a].push_back(i);
        match[b].push_back(i);
        cost.push_back(0);
    }

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

    int unite(int u, int v, int w) {
        u = get(u), v = get(v);
        if (u == v)
            return 0;

        int ret = 1;

        vector<int> &a = match[u], &b = match[v], c;
        while (a.size() || b.size()) {
            if (b.empty() || (a.size() && a.back() > b.back())) {
                c.push_back(a.back());
                a.pop_back();
            } else if (a.empty() || (b.size() && b.back() > a.back())) {
                c.push_back(b.back());
                b.pop_back();
            } else {
                cost[a.back()] = w;
                ret++;
                a.pop_back();
                b.pop_back();
            }
        }

        match[u] = c;
        dsu[v] = u;
        return ret;
    }
};

ll res = 0;
void dfs(int v = 0, int p = -1, ll sum = 0) {
    res += sum * sz[v];

    for (auto &[u, w] : adj[v]) {
        if (u != p) {
            dfs(u, v, sum + w);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> k;

    vector<array<int, 3>> e(m);
    for (auto &[w, u, v] : e)
        cin >> u >> v >> w;

    DSU2 dsu(n + 1);

    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;

        f[i] = {u, v};
        dsu.add(u, v, i);
    }

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    sort(all(e));

    DSU comp(n + 1);
    vector<array<int, 3>> rem;

    for (auto &[w, u, v] : e) {
        int here = dsu.unite(u, v, w);

        if (!here)
            continue;

        if (here == 1)
            comp.unite(u, v);
        else
            rem.push_back({u, v, w});
    }

    memset(head, -1, sizeof(head));

    int groupcnt = 0;
    for (int i = 1; i <= n; i++) {
        if (head[comp.get(i)] == -1)
            head[comp.get(i)] = groupcnt++;

        if (head[i] == -1)
            head[i] = head[comp.get(i)];
    }

    for (int i = 1; i <= n; i++) {
        sz[head[i]] += p[i];
    }

    for (int i = 0; i < k; i++) {
        auto &[u, v] = f[i];
        u = head[u], v = head[v];
    }

    for (auto &[u, v, w] : rem) {
        u = head[u], v = head[v];
    }

    ll ans = 0;
    for (int msk = 1; msk < (1 << k); msk++) {
        dsu = DSU2(k + 1);
        DSU bruh(k + 1);

        for (int i = 0; i < k; i++) {
            if (msk >> i & 1) {
                auto &[u, v] = f[i];

                dsu.add(u, v, i);
            }
        }

        bool ok = 1;

        for (auto &[u, v, w] : rem) {
            int here = dsu.unite(u, v, w);
            if (here == 1) {
                adj[u].push_back({v, 0});
                adj[v].push_back({u, 0});
                assert(bruh.unite(u, v));
            } else if (here > 2) {
                ok = 0;
                break;
            }
        }

        if (ok) {
            for (int i = 0; i < k; i++) {
                if (msk >> i & 1) {
                    auto &[u, v] = f[i];

                    int w = dsu.cost[i];
                    adj[u].push_back({v, w});
                    adj[v].push_back({u, w});
                    assert(bruh.unite(u, v));
                }
            }

            res = 0;
            dfs();
            ans = max(ans, res);
        }

        for (int i = 0; i <= k; i++) {
            adj[i].clear();
        }
    }

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22