Submission #1127876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127876		Pwo	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5093 ms	12200 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;
vector<int> bps;

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());
	bps.push_back(0); bps.push_back(edges[0].w);
	for (int i = 1; i < m; i++) {
		int bp = edges[i - 1].w + (edges[i].w - edges[i - 1].w + 1) / 2;
		if (bps.back() != bp) bps.push_back(bp);
		if (bps.back() != edges[i].w) bps.push_back(edges[i].w);
	}
	
	int split = -1, cost = 0, les = 0, bp = -1, prev = -1;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		int bp2 = lower_bound(bps.begin(), bps.end(), x) - bps.begin();
		if (bp2 == bp) {
			cout << cost + (2 * les - n + 1) * (x - prev) << '\n';
			continue;
		}
		bp = bp2;
		reset();
		while (split < m - 1 && edges[split + 1].w <= x) split++;
		int l = split, r = split + 1, took = 0; cost = 0, les = 0;
		while ((l >= 0 || r < m) && took < n - 1) {
			edge e;
			if (l >= 0 && r < m)
				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)) {
				if (e.w < x) les++;
				cost += abs(x - e.w);
				took++;
				merge(e.u, e.v);
			}
		}
		
		prev = x;
		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