Submission #1194002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194002		_callmelucian	Toll (APIO13_toll)	C++17	16 / 100	1270 ms	440 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define int long long

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

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

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    bool unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return 0;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        return 1;
    }
};

ll kruskal (vector<tpl> edges, int n) {
    sort(all(edges));
    DSU dsu(n);
    ll ans = 0;
    for (auto [c, a, b] : edges) {
        if (dsu.unite(a, b)) ans += c;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    vector<tpl> edge(m);
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        edge[i] = make_tuple(c, a, b);
    }

    vector<pii> newEdge(k);
    for (int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        newEdge[i] = make_pair(a, b);
    }

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

    ll mst = kruskal(edge, n), ans = 0;
    for (int tryWeight = 1; tryWeight <= 1'000'000; tryWeight++) {
        edge.emplace_back(tryWeight, newEdge[0].first, newEdge[0].second);
        if (kruskal(edge, n) <= mst) {
            DSU dsu1(n), dsu2(n);
            vector<tpl> edges = edge;
            sort(all(edges));
            for (auto cur : edges) {
                int c, a, b; tie(c, a, b) = cur;
                if (dsu1.unite(a, b) && cur != edge.back()) dsu2.unite(a, b);
            }

            ll cur = 0;
            for (int i = 1; i <= n; i++)
                if (dsu2.get(i) != dsu2.get(1)) cur += tryWeight * weight[i];
            ans = max(ans, cur);
        }
        edge.pop_back();
    }
    cout << ans;


    return 0;
}

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