Submission #951532

#	Time	Username	Problem	Language	Result	Execution time	Memory
951532		LittleOrange	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5079 ms	7216 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct dsu{
    vector<ll> p;
    dsu(ll N):p(N,-1){}
    ll g(ll x){return p[x]==-1?x:p[x]=g(p[x]);}
    bool m(ll a, ll b){
        a=g(a);b=g(b);
        if(a!=b)p[a]=b;
        return a!=b;
    }
};
struct edge{
    ll u,v,w;
    bool operator<(const edge& o) const{
        return w<o.w;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,m;
    cin >> n >> m;
    vector<edge> a(m);
    for(edge &o : a) cin >> o.u >> o.v >> o.w, o.u--,o.v--;
    ll q;
    cin >> q;
    while(q--){
        ll x;
        cin >> x;
        vector<edge> b = a;
        for(edge &o : b) o.w = abs(x-o.w);
        sort(b.begin(),b.end());
        ll ans = 0;
        dsu d(n);
        for(auto [u,v,w] : b){
            ans += w*d.m(u,v);
        }
        cout << ans << "\n";
    }
}

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