Submission #915359

#	Time	Username	Problem	Language	Result	Execution time	Memory
915359		Alcabel	Toll (APIO13_toll)	C++17	100 / 100	1114 ms	14072 KiB

toll

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

struct DSU {
    int n;
    vector<int> par, sz;
    DSU() {}
    DSU(int _n) {
        n = _n;
        par.resize(n);
        sz.resize(n);
        clear();
    }
    void clear() {
        for (int i = 0; i < n; ++i) {
            par[i] = i, sz[i] = 1;
        }
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    bool uniteSets(int v, int u) {
        v = getParent(v), u = getParent(u);
        if (v == u) { return false; }
        if (sz[v] < sz[u]) { swap(v, u); }
        par[u] = v;
        sz[v] += sz[u];
        return true;
    }
    ~DSU() {}
};

struct Edge {
    int v, u, w;
    Edge() {}
    Edge(int _v, int _u, int _w) {
        v = _v, u = _u, w = _w;
    }
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
    ~Edge() {}
};

vector<vector<pair<int, int>>> g;
vector<int> h, parW, par;
vector<long long> compP, sumP;

void dfsPrecalc(int v) {
    sumP[v] = compP[v];
    for (const auto& [u, newW] : g[v]) {
        if (u != par[v]) {
            parW[u] = newW;
            par[u] = v;
            h[u] = h[v] + 1;
            dfsPrecalc(u);
            sumP[v] += sumP[u];
        }
    }
    // cerr << "v: " << v << ", sumP: " << sumP[v] << ", compP: " << compP[v] << '\n';
}

void minEq(int v, int u, int w) {
    if (h[v] < h[u]) {
        swap(v, u);
    }
    while (h[v] > h[u]) {
        parW[v] = min(parW[v], w);
        v = par[v];
    }
    while (v != u) {
        parW[v] = min(parW[v], w);
        parW[u] = min(parW[u], w);
        v = par[v], u = par[u];
    }
}

long long dfsAns(int v) {
    long long res = parW[v] * sumP[v];
    for (const auto& [u, newW] : g[v]) {
        if (u != par[v]) {
            res += dfsAns(u);
        }
    }
    return res;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        --v, --u;
        edges[i] = Edge(v, u, w);
    }
    vector<Edge> additional(k);
    DSU with(n);
    for (int i = 0; i < k; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        additional[i] = Edge(v, u, 1000001);
        with.uniteSets(v, u);
    }
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    sort(edges.begin(), edges.end());
    DSU without(n);
    // cerr << "!\n";
    vector<Edge> mstEdges;
    for (int i = 0; i < m; ++i) {
        if (without.uniteSets(edges[i].v, edges[i].u)) {
            mstEdges.emplace_back(edges[i]);
        }
    }
    // cerr << "!\n";
    without.clear();
    vector<Edge> sus;
    for (const Edge& e : mstEdges) {
        if (with.getParent(e.v) != with.getParent(e.u)) {
            without.uniteSets(e.v, e.u);
        } else {
            sus.emplace_back(e);
        }
        with.uniteSets(e.v, e.u);
    }
    // cerr << "!\n";
    assert((int)sus.size() <= k);
    vector<int> compOf(n, -1);
    int comps = 0;
    for (int i = 0; i < n; ++i) {
        if (compOf[without.getParent(i)] == -1) {
            compOf[without.getParent(i)] = comps++;
            compP.emplace_back(0);
        }
        int c = compOf[without.getParent(i)];
        compOf[i] = c;
        compP[c] += p[i];
    }
    g.resize(comps);
    h.resize(comps);
    sumP.resize(comps);
    par.resize(comps);
    parW.resize(comps);
    for (Edge& e : sus) {
        e.v = compOf[e.v];
        e.u = compOf[e.u];
        assert(e.v != e.u);
    }
    for (Edge& e : additional) {
        e.v = compOf[e.v];
        e.u = compOf[e.u];
        assert(e.v != e.u);
    }
    long long ans = 0;
    DSU comp(comps);
    vector<Edge> limits;
    /*cerr << "!\n";
    for (int i = 0; i < n; ++i) {
        cerr << "i: " << i << ", compOf: " << compOf[i] << '\n';
    }*/
    for (int mask = 1; mask < (1 << k); ++mask) {
        comp.clear();
        for (int i = 0; i < comps; ++i) {
            g[i].clear();
        }
        bool hasCycle = false;
        for (int i = 0; i < k; ++i) {
            if (mask & (1 << i)) {
                if (!comp.uniteSets(additional[i].v, additional[i].u)) {
                    hasCycle = true;
                    break;
                }
                g[additional[i].v].emplace_back(additional[i].u, additional[i].w);
                g[additional[i].u].emplace_back(additional[i].v, additional[i].w);
            }
        }
        if (hasCycle) {
            continue;
        }
        // cerr << "mask: " << mask << ", dont have a cycle\n";
        limits.clear();
        for (const Edge& e : sus) {
            if (comp.uniteSets(e.v, e.u)) {
                g[e.v].emplace_back(e.u, 0);
                g[e.u].emplace_back(e.v, 0);
            } else {
                limits.emplace_back(e);
            }
        }
        h[compOf[0]] = 0;
        par[compOf[0]] = -1;
        parW[compOf[0]] = 0;
        // cerr << "dfsPrecalc:\n";
        dfsPrecalc(compOf[0]);
        for (const Edge& e : limits) {
            minEq(e.v, e.u, e.w);
        }
        ans = max(ans, dfsAns(compOf[0]));
    }
    cout << ans << '\n';
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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