Submission #1127531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127531		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5094 ms	4960 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define FOR(i, n) for(int i = 0; i < n; ++i)
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());

const int M = 1e5 + 5;
struct edge{
    int u, v, w;
} e[M];
int n, m, q;

struct DSU{
    int n;
    vi par, sz;
    DSU(int _n){
        n = _n;
        sz.assign(n + 1, 1);
        par.resize(n + 1);
        iota(all(par), 0);
    }
    int root(int u){
        return (par[u] == u? u : par[u] = root(par[u]));
    }
    void unite(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
    }
};

namespace sub12{
void go(){
    FOR(rep, q){
        int x; cin >> x;
        DSU dsu(n);
        sort(e + 1, e + m + 1, [&](edge a, edge b){
            return abs(a.w - x) < abs(b.w - x);
        });
        ll ans = 0;
        for(int i = 1; i <= m; ++i){
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if(dsu.root(u) != dsu.root(v)){
                dsu.unite(u, v);
                ans += abs(w - x);
            }
        }
        cout << ans << "\n";
    }
}
}

signed 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; i <= m; ++i){
        int u, v, w; cin >> u >> v >> w;
        e[i] = {u, v, w};
    }
    cin >> q;
    sub12::go();
    return 0;
}
/**
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4
**/

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