Submission #899852

#	Time	Username	Problem	Language	Result	Execution time	Memory
899852		TAhmed33	Reconstruction Project (JOI22_reconstruction)	C++98	3 / 100	5071 ms	12128 KiB

reconstruction

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 1;
array <int, 3> edges[MAXN];
int sze[MAXN], par[MAXN];
inline int abs (int x) {
	return x >= 0 ? x : -x;
}
inline void init (int n) {
	for (int i = 1; i <= n; i++) {
		sze[i] = 1; par[i] = i;
	}
}
inline int find (int x) {
	int u = x;
	while (par[u] != u) {
		u = par[u];
	}
	while (x != u) {
		int y = x; x = par[x]; par[y] = x;
	}
	return u;
}
ll sum; int x;
int comp;
inline void merge (int a, int b, int c) {
	a = find(a); b = find(b);
	if (a == b) return;
	comp--;
	sum += abs(c - x);
	if (sze[a] > sze[b]) swap(a, b);
	sze[b] += sze[a]; par[a] = b;
}
int n, m;
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[i] = {c, a, b};
	}
	sort(edges + 1, edges + m + 1);
	int ptr = 1;
	int q;
	cin >> q;
	while (q--) {
		cin >> x;
		if (m == 1) {
			cout << abs(x - edges[1][0]) << '\n';
			continue;
		}
		init(n); sum = 0;
		while (ptr + 1 <= m && abs(edges[ptr + 1][0] - x) <= abs(edges[ptr][0] - x)) ptr++;
		int l = ptr, r = ptr; comp = n;
		while ((l >= 1 || r <= m) && comp > 1) {
			if (l >= 1 && (r > m || abs(x - edges[l][0]) < abs(x - edges[r][0]))) {
				merge(edges[l][1], edges[l][2], edges[l][0]);
				l--;
			} else {
				merge(edges[r][1], edges[r][2], edges[r][0]);
				r++;
			}
		}
		cout << sum << '\n';
	}
}

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