Submission #1127920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127920		Pwo	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5094 ms	15516 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> g[505];
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;
		g[u].push_back(w);
		g[v].push_back(u);
		edges.push_back({u, v, w});
	}

	sort(edges.begin(), edges.end());
	bps.push_back(0);
	for (int i = 1; i < n; i++) {
		sort(g[i].begin(), g[i].end());
		bps.push_back(g[i][0]);
		for (size_t j = 1; j < g[i].size(); j++) {
			int idx = g[i][j - 1] + (g[i][j] - g[i][j - 1] + 1) / 2;
			bps.push_back(idx);
			bps.push_back(g[i][j]);
		}
	}
	//for (int i = 0; i < m; i++) {
	//	for (int j = i; j < m; j++) {
	//		int bp = edges[i].w + (edges[j].w - edges[i].w + 1) / 2;
	//		bps.push_back(bp);
	//	}
	//}
	sort(bps.begin(), bps.end());
	bps.erase(unique(bps.begin(), bps.end()), bps.end());
	
	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 = upper_bound(bps.begin(), bps.end(), x) - bps.begin() - 1;
		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