Submission #374184

#	Time	Username	Problem	Language	Result	Execution time	Memory
374184		dolphingarlic	Toll (APIO13_toll)	C++14	78 / 100	2572 ms	23132 KiB

toll

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

int n, m, k;
int u[300021], v[300021];
ll c[300021], p[100001];

int cmp1[100001], cmp2[100001];
int find(int A, int *cmp) { return (A == cmp[A] ? A : cmp[A] = find(cmp[A], cmp)); }
void onion(int A, int B, int *cmp) { cmp[find(A, cmp)] = find(B, cmp); }

vector<int> compressed;
vector<pair<int, ll>> graph[100001];
int root;
vector<tuple<ll, int, int>> critical;

bool assign(int node, int dest, ll weight, int parent = 0) {
    if (node == dest) return true;
    bool good = false;
    for (int i = 0; i < graph[node].size(); i++)
        if (graph[node][i].first != parent) {
            if (assign(graph[node][i].first, dest, weight, node)) {
                good = true;
                if (graph[node][i].second == -1)
                    graph[node][i].second = weight;
            }
    }
    return good;
}

pair<ll, ll> calc(int node, int parent = 0) {
    pair<ll, ll> ans = {0, p[node]};
    for (pair<int, ll> i : graph[node]) if (i.first != parent) {
        pair<ll, ll> tmp = calc(i.first, node);
        ans.first += tmp.first + tmp.second * i.second;
        ans.second += tmp.second;
    }
    return ans;
}

ll check(int mask) {
    // Reset the graph and the DSU
    for (int i : compressed) graph[i].clear(), cmp2[i] = i;

    // Onion stuff based on mask, and construct some edges in the graph
    for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
        if (find(u[m + i], cmp2) == find(v[m + i], cmp2)) return 0;
        graph[u[m + i]].push_back({v[m + i], -1});
        graph[v[m + i]].push_back({u[m + i], -1});
        onion(u[m + i], v[m + i], cmp2);
    }

    for (auto i : critical) {
        if (find(get<1>(i), cmp2) == find(get<2>(i), cmp2)) {
            // Assign weights to edges on the path between these two nodes
            assign(get<1>(i), get<2>(i), get<0>(i));
            assign(get<2>(i), get<1>(i), get<0>(i));
        } else {
            // Add an edge to the graph
            graph[get<1>(i)].push_back({get<2>(i), 0});
            graph[get<2>(i)].push_back({get<1>(i), 0});
            onion(get<1>(i), get<2>(i), cmp2);
        }
    }

    return calc(root).first;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> c[i];
    for (int i = 1; i <= k; i++) cin >> u[m + i] >> v[m + i];
    for (int i = 1; i <= n; i++) cin >> p[i];

    // Find the mandatory edges and collapse components together
    vector<tuple<ll, int, int>> edges;
    for (int i = 1; i <= m + k; i++) edges.push_back({c[i], u[i], v[i]});
    sort(edges.begin(), edges.end());
    iota(cmp1 + 1, cmp1 + n + 1, 1);
    iota(cmp2 + 1, cmp2 + n + 1, 1);
    for (auto i : edges) {
        if (find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
            if (get<0>(i)) {
                p[find(get<2>(i), cmp2)] += p[find(get<1>(i), cmp2)];
                onion(get<1>(i), get<2>(i), cmp2);
            }
            onion(get<1>(i), get<2>(i), cmp1);
        }
    }

    // Find the K + 1 component parents and the root after compression
    for (int i = 1; i <= n; i++) {
        cmp1[i] = cmp2[i];
        if (i == cmp2[i]) compressed.push_back(i);
    }
    root = find(1, cmp2);
    // Find the K "critical" edges
    for (auto i : edges) {
        if (get<0>(i) && find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
            critical.push_back(i);
            onion(get<1>(i), get<2>(i), cmp1);
        }
    }
    for (int i = 1; i <= n; i++) cmp1[i] = cmp2[i];

    // Re-index
    for (int i = 1; i <= k; i++) u[m + i] = find(u[m + i], cmp1), v[m + i] = find(v[m + i], cmp1);
    for (auto& i : critical) get<1>(i) = find(get<1>(i), cmp1), get<2>(i) = find(get<2>(i), cmp1);

    // Test each subset of edges
    ll ans = 0;
    for (int mask = 1; mask < (1 << k); mask++) ans = max(ans, check(mask));
    cout << ans;
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'bool assign(int, int, ll, int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < graph[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'll check(int)':
toll.cpp:47:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |     for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
      |                                                   ~~^~~

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