Submission #754919

#	Time	Username	Problem	Language	Result	Execution time	Memory
754919		Lobo	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5086 ms	811708 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;
		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;
		dsuclear();

		int p = 0;
		int q = 0;

		while((id != 0 && p != vecl[id-1].size()) || (id != m && q != vecr[id].size())) {
			if(id == 0 || p == vecl[id-1].size()) {
				int w = edgs[vecr[id][q]].fr;
				int u = edgs[vecr[id][q]].sc.fr;
				int v = edgs[vecr[id][q]].sc.sc;
				q++;
				edg.pb(mp(w-k,mp(u,v)));
			}
			else if(id == m || q == vecr[id].size()) {
				int w = edgs[vecl[id-1][p]].fr;
				int u = edgs[vecl[id-1][p]].sc.fr;
				int v = edgs[vecl[id-1][p]].sc.sc;
				p++;
				edg.pb(mp(k-w,mp(u,v)));
			}
			else if(edgs[vecr[id][q]].fr-k <= k-edgs[vecl[id-1][p]].fr) {
				int w = edgs[vecr[id][q]].fr;
				int u = edgs[vecr[id][q]].sc.fr;
				int v = edgs[vecr[id][q]].sc.sc;
				q++;
				edg.pb(mp(w-k,mp(u,v)));
			}
			else {
				int w = edgs[vecl[id-1][p]].fr;
				int u = edgs[vecl[id-1][p]].sc.fr;
				int v = edgs[vecl[id-1][p]].sc.sc;
				p++;
				edg.pb(mp(k-w,mp(u,v)));
			}
		}

		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;
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:111:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   while((id != 0 && p != vecl[id-1].size()) || (id != m && q != vecr[id].size())) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:111:62: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   while((id != 0 && p != vecl[id-1].size()) || (id != m && q != vecr[id].size())) {
      |                                                            ~~^~~~~~~~~~~~~~~~~~
reconstruction.cpp:112:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    if(id == 0 || p == vecl[id-1].size()) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:119:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    else if(id == m || q == vecr[id].size()) {
      |                       ~~^~~~~~~~~~~~~~~~~~

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