Submission #1198032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198032		LucaIlie	Reconstruction Project (JOI22_reconstruction)	C++20	42 / 100	5097 ms	413672 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

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

struct DSU {
    vector<int> parent;

    void init(int n) {
        parent.clear();
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }

    int findParent(int v) {
        if (parent[v] != v)
            parent[v] = findParent(parent[v]);
        return parent[v];
    }

    void connect(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        if (u == v)
            return;
        parent[v] = u;
    }

    bool connected(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        return (u == v);
    }
};

const int MAX_N = 500;
const int MAX_M = 1e5;
const int MAX_Q = 1e6;
vector<int> importantEdgesLower[MAX_M + 1], importantEdgesGreater[MAX_M + 2];
edge edges[MAX_M + 1];
DSU dsu;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    cin >> n >> m;
    for (int e = 1; e <= m; e++)
        cin >> edges[e].u >> edges[e].v >> edges[e].w;

    sort(edges + 1, edges + 1 + m, [](edge a, edge b) {
        return a.w < b.w;
    });

    for (int e = 1; e <= m; e++) {
        dsu.init(n);
        dsu.connect(edges[e].u, edges[e].v);
        importantEdgesLower[e].push_back(e);
        for (int f: importantEdgesLower[e - 1]) {
            if (!dsu.connected(edges[f].u, edges[f].v)) {
                dsu.connect(edges[f].u, edges[f].v);
                importantEdgesLower[e].push_back(f);
            }
        }
    }

    for (int e = m; e >= 1; e--) {
        dsu.init(n);
        dsu.connect(edges[e].u, edges[e].v);
        importantEdgesGreater[e].push_back(e);
        for (int f: importantEdgesGreater[e + 1]) {
            if (!dsu.connected(edges[f].u, edges[f].v)) {
                dsu.connect(edges[f].u, edges[f].v);
                importantEdgesGreater[e].push_back(f);
            }
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int w;
        cin >> w;

        int l = 0, r = m + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (edges[mid].w > w)
                r = mid;
            else
                l = mid;
        }

        dsu.init(n);
        int j = 0;
        long long cost = 0;
        for (int e: importantEdgesLower[l]) {
            while (j < (int)importantEdgesGreater[r].size() && edges[importantEdgesGreater[r][j]].w - w < w - edges[e].w) {
                int f = importantEdgesGreater[r][j];
                if (!dsu.connected(edges[f].u, edges[f].v)) {
                    dsu.connect(edges[f].u, edges[f].v);
                    cost += edges[f].w - w;
                }
                j++;
            }
            if (!dsu.connected(edges[e].u, edges[e].v)) {
                dsu.connect(edges[e].u, edges[e].v);
                cost += w - edges[e].w;
            }
        }
        while (j < (int)importantEdgesGreater[r].size()) {
            int f = importantEdgesGreater[r][j];
            if (!dsu.connected(edges[f].u, edges[f].v)) {
                dsu.connect(edges[f].u, edges[f].v);
                cost += edges[f].w - w;
            }
            j++;
        }

        cout << cost << "\n";
    }

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23