Submission #1223217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223217		BestCrazyNoob	Toll (APIO13_toll)	C++20	0 / 100	0 ms	324 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct DSU {
    vector<int> p, s;
    DSU(int N) {
        s.resize(N, 1);
        p.resize(N);
        for (int i = 0; i < N; i++) p[i] = i;
    }
    int repr(int a) {
        while (p[a] != a) a = p[a];
        return a;
    }
    bool join(int a, int b) {
        a = repr(a);
        b = repr(b);
        if (a == b) return false;
        if (s[a] < s[b]) swap(a, b);
        s[a] += s[b];
        p[b] = a;
        return true;
    }
};

struct Edge {
    int i, j, w;
};

int N, M, K;
vector<vector<pii>> tree;
vector<int> P;
ll res = 0;

bool setup(int curr, int prev, int tar, int w) {
    if (curr == tar) return true;
    for (auto &[c, cw]: tree[curr]) {
        if (c == prev) continue;
        if (setup(c, curr, tar, w)) {
            if (cw == -1) cw = w;
            return true;
        }
    }
    return false;
}

ll eval(int curr, int prev) {
    ll up = P[curr];
    for (auto [c, w]: tree[curr]) {
        if (c == prev) continue;
        const ll upc = eval(c, curr);
        res += w * upc;
        up += upc;
    }
    return up;
}

int main() {
    cin >> N >> M >> K;
    vector<Edge> edges(M);
    for (Edge &e: edges) {
        cin >> e.i >> e.j >> e.w;
        e.i--; e.j--;
    }
    vector<pii> add(K);
    for (pii &e: add) {
        cin >> e.first >> e.second;
        e.first--; e.second--;
    }
    P.resize(N);
    for (int &x: P) cin >> x;
    
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {return a.w < b.w;});

    ll ans = 0;

    for (int mask = 0; mask < (1 << K); mask++) {
        tree.clear();
        tree.resize(N);
        int edgeCnt = 0;
        bool cycle = false;
        for (int h = 0; h < K; h++) {
            if (((mask >> h) & 1)) {
                if (setup(add[h].first, -1, add[h].second, -1)) {
                    cycle = true;
                    break;
                }
                tree[add[h].first].push_back({add[h].second, -1});
                tree[add[h].second].push_back({add[h].first, -1});
                edgeCnt++;
            }
        }

        if (cycle) continue;

        for (Edge e: edges) {
            if (!setup(e.i, -1, e.j, e.w)) {
                edgeCnt++;
                tree[e.i].push_back({e.j, 0});
                tree[e.j].push_back({e.i, 0});
            }
        }

        res = 0;
        eval(0, -1);
        ans = max(ans, res);
    }

    cout << ans << '\n';

    return 0;
}

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