Submission #754909

#	Time	Username	Problem	Language	Result	Execution time	Memory
754909		Lobo	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5073 ms	811108 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int maxn = 550;
const int maxm = 1e5+10;

int n, m, ds[maxn], dsz[maxn];
vector<int> vecl[maxm], vecr[maxm];

int find(int v) {
	if(v == ds[v]) return v;
	return ds[v] = find(ds[v]);
}

void join(int u, int v) {
	if(dsz[u] < dsz[v]) swap(u,v);
	dsz[u]+= dsz[v];
	ds[v] = u;
}

void dsuclear() {
	for(int i = 1; i <= n; i++) {
		ds[i] = i;
		dsz[i] = 1;
	}
}

int32_t main() {
	// freopen("in.in","r",stdin);

	cin >> n >> m;

	vector<pair<int,pair<int,int>>> edgs;
	for(int i = 1; i <= m; i++) {
		int u,v,w; cin >> u >> v >> w;

		edgs.pb(mp(w,mp(u,v)));
	}

	sort(all(edgs));
	for(int i = 0; i < m; i++) {
		dsuclear();
		vecl[i].pb(i);
		join(edgs[i].sc.fr,edgs[i].sc.sc);
		if(i != 0) {
			for(auto id : vecl[i-1]) {
				int u = edgs[id].sc.fr;
				int v = edgs[id].sc.sc;
				u = find(u);
				v = find(v);
				if(u != v) {
					vecl[i].pb(id);
					join(u,v);
				}
			}
		}
	}

	for(int i = m-1; i >= 0; i--) {
		dsuclear();
		vecr[i].pb(i);
		join(edgs[i].sc.fr,edgs[i].sc.sc);
		if(i != m-1) {
			for(auto id : vecr[i+1]) {
				int u = edgs[id].sc.fr;
				int v = edgs[id].sc.sc;
				u = find(u);
				v = find(v);
				if(u != v) {
					vecr[i].pb(id);
					join(u,v);
				}
			}
		}
	}

	int q; cin >> q;

	while(q--) {
		int k; cin >> k;

		int ans = 0;

		int id;
		int lbs = 0;
		int rbs = m-1;
		id = m-1;
		while(lbs <= rbs) {
			int mid = (lbs+rbs)>>1;

			if(edgs[mid].fr >= k) {
				id = mid;
				rbs = mid-1;
			}
			else {
				lbs = mid+1;
			}
		}
		vector<pair<int,pair<int,int>>> edg;

		if(id != 0) {
			for(auto i : vecl[id-1]) {
				int w = edgs[i].fr;
				int u = edgs[i].sc.fr;
				int v = edgs[i].sc.sc;

				if(k >= w) edg.pb(mp(k-w,mp(u,v)));
				else edg.pb(mp(w-k,mp(u,v)));

			}
		}

		for(auto i : vecr[id]) {
			int w = edgs[i].fr;
			int u = edgs[i].sc.fr;
			int v = edgs[i].sc.sc;

			if(k >= w) edg.pb(mp(k-w,mp(u,v)));
			else edg.pb(mp(w-k,mp(u,v)));

		}

		sort(all(edg));

		dsuclear();
		for(auto X : edg) {
			int w = X.fr;
			int u = X.sc.fr;
			int v = X.sc.sc;
			u = find(u);
			v = find(v);
			if(u != v) {
				ans+= w;
				join(u,v);
			}
		}

		cout << ans << endl;
	}
}

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