Submission #1029719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029719		mansur	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5090 ms	6380 KiB

reconstruction

#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin() s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1000;

int pr[N], sz[N];

int get(int x) {
	if (pr[x] == x) return x;
	return pr[x] = get(pr[x]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<array<int, 3>> g;
	while (m--) {
		int a, b, w;
		cin >> a >> b >> w;
		g.push_back({w, a, b});
	}
	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		if (m == n - 1) {
			ll ans = 0;
			for (auto [w, a, b]: g) ans += abs(w - x);
			cout << ans << '\n';
			continue;
		}
		for (int i = 1; i <= n; i++) {
			pr[i] = i, sz[i] = 1;
		}
		vector<array<int, 3>> gr;
		for (auto [w, a, b]: g) {
			gr.push_back({abs(w - x), a, b});
		}
		sort(all(gr));
		ll ans = 0;
		for (auto [w, a, b]: gr) {
			a = get(a), b = get(b);
			if (a == b) continue;
			if (sz[a] > sz[b]) swap(a, b);
			ans += w, pr[a] = b, sz[b] += sz[a];
		}         
		cout << ans << '\n';
	}
}

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