Submission #779808

#	Time	Username	Problem	Language	Result	Execution time	Memory
779808		aZvezda	Reconstruction Project (JOI22_reconstruction)	C++14	0 / 100	1 ms	980 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif

const ll MAX_N = 1e4 + 10; 
ll n, m;
pair<ll, pair<ll, ll> > edg[MAX_N];

struct {
	ll par[MAX_N], sz[MAX_N];
	vector<ll> now;

	void reset() {
		for(ll i = 1; i <= n; i ++) {
			par[i] = i;
			sz[i] = 1;
		}
		now.resize(0);
	}

	ll find(ll x) {
		if(par[x] == x) {
			return x;
		} else {
			return par[x] = find(par[x]);
		}
	}

	void merge(ll x, ll y, ll c) {
		x = find(x); y = find(y);
		if(x == y) { return; }
		if(sz[x] < sz[y]) { swap(x, y); }
		par[y] = x;
		sz[x] += sz[y];
		now.push_back(c);
	}
} dsu;

vector<ll> cand[MAX_N];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;
	for(ll i = 0; i < m; i ++) {
		cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first;
		edg[m + i] = edg[i];
	}

	sort(edg, edg + m);
	sort(edg + m, edg + 2 * m);
	reverse(edg + m, edg + 2 * m);

	m = 2 * m;

	dsu.reset();
	for(ll i = 0; i < m; i ++) {
		dsu.reset();
		dsu.merge(edg[i].second.first, edg[i].second.second, i);
		if(i != 0) for(const auto j : cand[i - 1]) {
			dsu.merge(edg[j].second.first, edg[j].second.second, j);
		}
		cand[i] = dsu.now;
	}

	for(int i = 0; i < m; i ++) {
		if(cand[i].size() == 0) { continue; }
		for(auto j : cand[i]) {
			cerr << edg[j].second.first << "," << edg[j].second.second << " ";
		}
		cerr << endl;
	}

	ll q;
	cin >> q;
	while(q --) {
		ll x;
		cin >> x;
		ll ans = 1e18;
		for(ll i = 0; i < m; i ++) {
			if(cand[i].size() != n - 1) { continue; }
			ll curr = 0;
			for(const auto j : cand[i]) {
				curr += abs(edg[j].first - x);
			}
			ans = min(ans, curr);
		}
		cout << ans << endl;
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:84:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   84 |    if(cand[i].size() != n - 1) { continue; }
      |       ~~~~~~~~~~~~~~~^~~~~~~~

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