Submission #905100

#	Time	Username	Problem	Language	Result	Execution time	Memory
905100		Ahmed57	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5066 ms	6808 KiB

reconstruction

//#include "dango3.h"

#include <bits/stdc++.h>
using namespace std;
int pr[501],gs[501];
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
    a = find(a);b = find(b);
    if(a==b)return 0;
    if(gs[a]<gs[b])swap(a,b);
    pr[b] = a;
    gs[a]+=gs[b];
    return 1;
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,m;
    cin>>n>>m;
    vector<array<int,3>> ed;
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        ed.push_back({a,b,c});
    }
    int q;
    cin>>q;
    while(q--){
        int c;
        cin>>c;
        vector<array<int,3>> lol;
        for(int i = 1;i<=n;i++){
            pr[i] = i , gs[i] = 1;
        }
        for(int i = 0;i<m;i++){
            lol.push_back({abs(ed[i][2]-c),ed[i][0],ed[i][1]});
        }
        sort(lol.begin(),lol.end());
        long long all = 0;
        for(auto i:lol){
            if(mergegroup(i[1],i[2])){
                all+=i[0];
            }
        }
        cout<<all<<endl;
    }
}

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