제출 #1127537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127537		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5093 ms	3824 KiB

reconstruction

#include <bits/stdc++.h>
#define SZ(a) (int)(a).size()
#define all(a) begin(a), end(a)
using ll = long long;
const int mxn = 1e5 + 3;
const int inf32 = 2e9;
const ll inf64 = 5e18;
const ll mod = 1e9 + 7;
using namespace std;
using Edge = tuple<int, int, int>;
int n, m, q;
vector<Edge> edges, new_edges;
int par[mxn], sz[mxn];
void init(){
	for (int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
}
int find(int u){
	return u == par[u] ? u : par[u] = find(par[u]);
}
bool join(int u, int v){
	u = find(u), v = find(v);
	if (u == v) return true;
	if (sz[u] < sz[v]) swap(u, v);
	sz[u] += sz[v], par[v] = u;
	return false;
}
void sub12(){
	while(q--){
		new_edges.clear();
		int x;
		cin >> x;
		for (auto e : edges){
			int w, u, v; tie(w, u, v) = e;
			new_edges.emplace_back(abs(w - x), u, v);
		}
		sort(all(new_edges));
		init();
		ll res = 0;
		for (auto e : new_edges){
			int w, u, v; tie(w, u, v) = e;
			if (!join(u, v)) res += w;
		}
		cout << res << '\n';
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
// 	freopen("railroad.inp", "r", stdin);
// 	freopen("railroad.out", "w", stdout);
	cin >> n >> m;
	for (int i = 0, u, v, w; i < m; ++i){
		cin >> u >> v >> w;
		edges.emplace_back(w, u, v);
	}
	cin >> q;
	sub12();
	return 0;
}

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