제출 #1128307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128307		Pwo	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2541 ms	20704 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, cur, pre;
vector<pair<int, pair<int, int>>> events;
multiset<int> active;

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]);
}

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

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());
	
	reset();
	for (int i = 0; i < m; i++) {
		if (merge(edges[i].u, edges[i].v)) {
			active.insert(edges[i].w);
			if ((int) active.size() >= n - 1) break;
		}
	}

	for (int i = 0; i < m; i++) {
		reset();
		merge(edges[i].u, edges[i].v);
		cur.clear();
		cur.push_back(edges[i]);
		for (const auto e : pre) {
			if (merge(e.u, e.v)) cur.push_back(e);
			else {
				int md = (edges[i].w + e.w + 1) / 2;
				events.push_back({md, {0, edges[i].w}}); // add
				events.push_back({md, {1, e.w}}); // remove
			}
		}
		pre = cur;
	}
	
	sort(events.begin(), events.end());
	
	int ptr = -1;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		while (ptr + 1 < (int) events.size() && events[ptr + 1].first <= x) {
			ptr++;
			if (events[ptr].second.first)
				active.erase(active.find(events[ptr].second.second));
			else
				active.insert(events[ptr].second.second);
		}
		int cost = 0;
		for (const auto u : active) cost += abs(u - x);
		cout << cost << '\n';
	}
}

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