Submission #911888

#	Time	Username	Problem	Language	Result	Execution time	Memory
911888		arashMLG	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5050 ms	10840 KiB

reconstruction

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

typedef long long       ll;
typedef pair<int,int>   pii;
typedef pair<ll,ll>     pll;

const int  N = 5e5 + 23;
const ll inf = 1e18;


#define F          first
#define S          second
#define pb         push_back
#define sz(x)      ((int)x.size())
#define kill(x)    cout<< x , exit(0);
#define all(x)     x.begin(),x.end()
#define lc         (v<<1)
#define rc         ((v<<1)|1)

struct DSU {
	int par[N];
	int s[N];
	
	void clear(int n) {
		iota(par,par+n+1,0);
		fill(s,s+n+1,1);
	}
	
	int getPar(int v) {
		return (par[v] == v ? v : par[v] = getPar(par[v]));
	}
	
	bool merge(int v,int u) {
		v = getPar(v),u = getPar(u);
		if(v == u) return false;
		if(s[v] > s[u]) swap(v,u);
		par[v] = u;
		s[u] += s[v];
		return true;
	}
} ds;

int n,m;
vector<int> comp;
vector<pair<int,pii>> edges;
pair<int,pii> E[N];

ll calc(int W) {
	edges.clear();
	ds.clear(n);
	for(int i =0 ; i < m;i ++) {
		edges.pb( { abs(E[i].F - W) , E[i].S});
	}
	sort(all(edges));
	ll ans= 0;
	for(auto [w,e]: edges) {
		if(ds.merge(e.F,e.S)) ans += w;
	}
	return ans;
}

int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i = 0 ; i < m; i ++) {
		int v,u,w; cin>>v>>u>>w;
		comp.pb(w);
		E[i]= {w,{v,u}};
	}
	int q; cin>>q;
	while(q--) {
		int x; cin>>x; cout<<calc(x) << '\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