Submission #1158065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158065		dombly	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5093 ms	8224 KiB

reconstruction

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e8;

struct DSU {
    vector<int>par;
    void init(int n) {
        par.resize(n + 10);
        for(int i = 1; i <= n; i++) par[i] = i;
    }
    int get(int x) {
        return (x == par[x] ? x : par[x] = get(par[x]));
    }
    void unite(int u,int v) {
        u = get(u); v = get(v);
        if(u == v) return;
        par[u] = v;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin >> n >> m;
    vector<array<int,3>>e(m + 1);
    for(int i = 1; i <= m; i++) cin >> e[i][0] >> e[i][1] >> e[i][2];
    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        vector<array<int,3>>f;
        for(int i = 1; i <= m; i++) f.pb({abs(x - e[i][2]),e[i][0],e[i][1]});
        sort(f.begin(),f.end());
        DSU dsu;
        dsu.init(n);
        int ans = 0;
        for(auto [w,u,v] : f) {
            if(dsu.get(u) != dsu.get(v)) {
                ans += w;
                dsu.unite(u,v);
            }
        }
        cout << ans << "\n";
    }
    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