Submission #726141

#	Time	Username	Problem	Language	Result	Execution time	Memory
726141		LOLOLO	Toll (APIO13_toll)	C++17	0 / 100	1 ms	212 KiB

toll

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
const int N = 1e6;

ll P[N];

struct DSU {
    vector<ll> e, sum;
    DSU(int N) { e = vector<ll>(N, -1); sum.resize(N); for (int i = 1; i < N; i++) sum[i] = P[i];}

    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)]; }

    ll add(int x) { return sum[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;
        sum[x] = sum[x] + sum[y];
        return true;
    }
};

struct edge{
    ll u, v, w;
};

bool cmp(edge A, edge B) {
    return A.w < B.w;
}

vector <edge> ed;

int n;

ll solve(vector <pair <ll, ll>> need) {
    DSU D(n + 1);
    ll ans = 0;

    for (auto x : ed) {
        bool is = 0;

        if (D.get(x.u) == D.get(x.v))
            continue;

        ll add = 0;

        if (D.same_set(x.u, 1) == 0) {
            add += D.add(x.u);
        }

        if (D.same_set(x.v, 1) == 0) {
            add += D.add(x.v);
        }

        D.unite(x.u, x.v);

        for (auto p : need) {
            if (!p.f) 
                continue;

            if (D.same_set(p.f, p.s)) {
                p.f = p.s = 0;
                is = 1;
            }
        }

        if (is) {
            ans += add * x.w;
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, k;

    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ed.push_back({u, v, w});
    }

    sort(ed.begin(), ed.end(), cmp);

    vector <pair <ll, ll>> add(k);

    for (int i = 0; i < k; i++)
        cin >> add[i].f >> add[i].s;

    for (int i = 1; i <= n; i++) {
        cin >> P[i];
    }

    ll ans = 0;

    for (int mask = 0; mask < (1 << k); mask++) {
        vector <pair <ll, ll>> need;
        for (int j = 0; j < k; j++) {
            if (mask & (1 << j)) need.push_back(add[j]);
        }

        ans = max(ans, solve(need));
    }

    cout << ans << "\n";
}

/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

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