Submission #951563

#	Time	Username	Problem	Language	Result	Execution time	Memory
951563		pcc	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5060 ms	4416 KiB

reconstruction

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

#define ll long long
#define al3 array<ll,3>

const int mxn = 1e5+10;
int N,M,Q;
array<ll,3> edges[mxn];

struct DSU{
	int dsu[550],sz[550];
	void init(int n){
		for(int i = 0;i<=n;i++){
			dsu[i] = i;
			sz[i] = 1;
		}
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		 a = root(a),b = root(b);
		 if(a == b)return;
		 if(sz[a]<sz[b])swap(a,b);
		 dsu[b] = a;
		 sz[a] += sz[b];
		 return;
	}
};
DSU dsu;

void solve(){
	ll K;
	cin>>K;
	sort(edges,edges+M,[&](al3 &a,al3 &b){return abs(a[0]-K)<abs(b[0]-K);});
	dsu.init(N);
	ll ans = 0;
	for(int i = 0;i<M;i++){
		auto [w,a,b] = edges[i];
		if(dsu.root(a) == dsu.root(b))continue;
		ans += abs(w-K);
		dsu.onion(a,b);
	}
	cout<<ans<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edges[i] = array<ll,3>({c,a,b});
	}
	cin>>Q;
	while(Q--)solve();
}

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