Submission #562443

#	Time	Username	Problem	Language	Result	Execution time	Memory
562443		DanShaders	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1107 ms	28516 KiB

reconstruction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 510;

struct DSU {
	int rank[N], parent[N];

	DSU() {
		clear();
	}

	void clear() {
		fill(all(rank), 0);
		iota(all(parent), 0);
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}

	void merge(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return;
		}
		if (rank[a] == rank[b]) {
			++rank[a];
		}
		if (rank[a] < rank[b]) {
			swap(a, b);
		}
		parent[b] = a;
	}
} dsu;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back({w, --u, --v});
	}
	sort(all(edges));
	vector<tuple<int, int, int>> events;
	ll bk = -1, bb = get<0>(edges[0]);
	for (int i = 0; i < m; ++i) {
		dsu.clear();
		auto [w, u, v] = edges[i];
		events.push_back({2 * w, 2, -2 * w});
		for (int j = i - 1; j >= 0; --j) {
			auto [wp, up, vp] = edges[j];
			dsu.merge(up, vp);
			if (dsu.get(u) == dsu.get(v)) {
				events.push_back({w + wp, -2, w + wp});
				break;
			} else if (j == 0) {
				--bk;
				bb += w;
			}
		}
	}
	sort(all(events));
	int it = 0;
	int queries;
	cin >> queries;
	while (queries--) {
		int x;
		cin >> x;
		while (it < sz(events) && get<0>(events[it]) <= 2 * x) {
			auto [_, dk, db] = events[it++];
			bk += dk;
			bb += db;
		}
		cout << ll(bk) * x + bb << "\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