Submission #1127533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127533		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5095 ms	27304 KiB

reconstruction

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

const int N = 501, M = 1e6 + 1;

struct DSU {
    vector<int> lab;

    DSU(int n) : lab(n + 1, -1) {}

    int find_set(int u) {
        return (lab[u] < 0) ? u : (lab[u] = find_set(lab[u]));
    }

    bool union_sets(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if(u == v) return 0;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return 1;
    }
};

struct Edge {
    int u, v, w;

    bool operator<(const Edge& rhs) const {
        if(w != rhs.w) return w < rhs.w;
        if(u != rhs.u) return u < rhs.u;
        return v < rhs.v;
    }

    bool operator==(const Edge& rhs) const {
        return (u == rhs.u) && (v == rhs.v) && (w == rhs.w);
    }
};

int n, m, q;
pair<vector<int>, int> c[N][N];

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

    // freopen("RAILROAD.inp", "r", stdin);
    // freopen("RAILROAD.out", "w", stdout);

    cin >> n >> m;
    for(int i = 1, u, v, w; i <= m; ++i) {
        cin >> u >> v >> w;
        if(u > v) swap(u, v);
        c[u][v].first.push_back(w);
    }
    set<Edge> avail, cur;
    for(int u = 1; u < n; ++u) {
        for(int v = u + 1; v <= n; ++v) {
            if(!c[u][v].first.empty()) {
                sort(c[u][v].first.begin(), c[u][v].first.end());
                cur.insert({u, v, c[u][v].first[0]});
                avail.insert({u, v, 0});
            }
        }
    }
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        vector<Edge> del;
        for(const Edge& e : avail) {
            int u = e.u, v = e.v;
            int& i = c[u][v].second;
            int tmp = i;
            while(i + 1 < c[u][v].first.size() && abs(x - c[u][v].first[i]) >= abs(x - c[u][v].first[i + 1])) ++i;
            if(i > tmp) {
                cur.erase({u, v, c[u][v].first[tmp]});
                cur.insert({u, v, c[u][v].first[i]});
            }
            if(i == c[u][v].first.size() - 1) del.push_back(e);
        }
        for(const Edge& e : del) avail.erase(e);
        vector<Edge> tmp;
        for(const Edge& e : cur) {
            tmp.push_back(e);
            tmp.back().w = abs(x - tmp.back().w);
        }
        sort(tmp.begin(), tmp.end());
        long long res = 0;
        DSU dsu(n);
        for(const Edge& e : tmp)
            if(dsu.union_sets(e.u, e.v)) res += e.w;
        cout << res << endl;
    }

    return 0;
}

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