Submission #547450

#	Time	Username	Problem	Language	Result	Execution time	Memory
547450		skittles1412	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	988 ms	37544 KiB

reconstruction

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct DSU {
	vector<int> p;

	DSU(int n) : p(n, -1) {}

	int find(int u) {
		return p[u] < 0 ? u : (p[u] = find(p[u]));
	}

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

	bool conn(int u, int v) {
		return find(u) == find(v);
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	array<int, 3> edges[m];
	for (auto& [w, u, v] : edges) {
		cin >> u >> v >> w;
		u--;
		v--;
	}
	sort(edges, edges + m);
	vector<array<int, 3>> changes;
	for (int i = 0; i < m; i++) {
		auto& [w, u, v] = edges[i];
		changes.push_back({w, 2, -2 * w});
		{
			int j;
			DSU dsu(n);
			for (j = i - 1; j >= 0; j--) {
				dsu.merge(edges[j][1], edges[j][2]);
				if (dsu.conn(u, v)) {
					break;
				}
			}
			int a = -1, b = w;
			if (j != -1) {
				a += -1;
				b += edges[j][0];
			}
			changes.push_back({j == -1 ? -1 : (w + edges[j][0] + 1) / 2, a, b});
		}
	}
	sort(begin(changes), end(changes));
	int q;
	cin >> q;
	long ans[q];
	vector<pair<int, int>> queries;
	for (int i = 0; i < q; i++) {
		int x;
		cin >> x;
		queries.emplace_back(x, i);
	}
	sort(begin(queries), end(queries));
	long ca = 0, cb = 0;
	int j = 0;
	for (auto& [x, qi] : queries) {
		while (j < sz(changes) && changes[j][0] <= x) {
			ca += changes[j][1];
			cb += changes[j][2];
			j++;
		}
		ans[qi] = ca * x + cb;
	}
	for (auto& a : ans) {
		cout << a << endl;
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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