Submission #1127392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127392		Pwo	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	1 ms	324 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct edge {
	int u, v, w;
	bool operator<(edge const& other) {
		return w < other.w;
	}
};

int n, m, q, p[505], sz[505];
vector<edge> edges;

void reset() {
	for (int i = 1; i <= n; i++)
		p[i] = i, sz[i] = 1;
}

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

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);
	p[v] = u;
	sz[u] += sz[v];
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		edges.push_back({u, v, w});
	}

	sort(edges.begin(), edges.end());
	
	int split = -1; cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x; reset();
		while (split < (int) edges.size() && edges[split + 1].w <= x) split++;
		int l = split, r = split + 1, took = 0, cost = 0;
		while ((l >= 0 || r < edges.size()) && took < n - 1) {
			edge e;
			if (l >= 0 && r < edges.size())
				e = (x - edges[l].w < edges[r].w - x ? edges[l--] : edges[r++]);
			else if (l >= 0) e = edges[l--];
			else e = edges[r++];
			if (find(e.u) != find(e.v)) {
				cost += abs(x - e.w);
				took++;
				merge(e.u, e.v);
			}
		}
		cout << cost << '\n';
	}
}

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