Submission #1139468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139468		NK_	Reconstruction Project (JOI22_reconstruction)	C++20	42 / 100	5095 ms	34796 KiB

reconstruction

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define bk back()

using ll = long long;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;
using vl = V<ll>;
using T = AR<int, 3>;

const ll INF = 1e15;

struct DSU {
	int N; vi e; V<T> took; void init(int n) { N = n; e = vi(N, -1); took = {}; }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y, int w) {
		int rx = get(x), ry = get(y);
		if (rx == ry) return 0;
		// cout << "ADDED: " << x << " " << y << " => " << w << endl;
		took.pb(T{w, x, y});
		if (e[rx] > e[ry]) swap(rx, ry);
		e[rx] += e[ry]; e[ry] = rx; return 1;
	}
};	

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	V<T> E; for(int i = 0; i < M; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		E.pb(T{w, u, v});
	}

	sort(begin(E), end(E));

	V<DSU> P = {DSU()}, S = {DSU()}; DSU D; ll ans = 0;

	V<V<AR<ll, 2>>> answer(M);
	int Q, cur = 0; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int x; cin >> x;

		while(cur < M && x > E[cur][0]) cur++;

		answer[min(cur, M - 1)].pb(AR<ll, 2>{x, q});
	}

	auto tri = [&](T e, ll at) { 
		if (D.unite(e[1], e[2], e[0])) {
			// cout << "TOOK: " << e[0] << " " << e[1] << " " << e[2] << endl;
			ans += abs(e[0] - at); 
		}
	};

	vl ANS(Q);
	function<void(int, int)> dnc = [&](int l, int r) {
		if (l == r) {
			S.bk.took.insert(begin(S.bk.took), E[l]);
			// cout << "L: " << E[l][0] << " " << E[l][1] << " " << E[l][2] << endl;

			int np = sz(P.bk.took), ns = sz(S.bk.took);
			for(auto& [at, i] : answer[l]) {
		
				// cout << "COMPUTE: " << l << " " << r << " -> " << at << " " << i << endl;

				D.init(N); ans = 0;
				int p = 0, s = 0;

				// cout << "START -> " << np << " " << ns << endl;

				while(p < np || s < ns) {
					if (sz(D.took) == N - 1) break;
					// cout << p << " " << s << endl;
					if (p == np) tri(S.bk.took[s++], at);
					else if (s == ns) tri(P.bk.took[p++], at);
					else if (abs(S.bk.took[s][0] - at) < abs(P.bk.took[p][0] - at)) {
						tri(S.bk.took[s++], at);
					} else {
						tri(P.bk.took[p++], at);
					}
				}

				// cout << "DONE => " << ans << endl;
				ANS[i] = ans;
			}

			return;
		}

		// cout << l << " <-----> " << r << endl;

		int m = (l + r) / 2;

		// go to [l, m] and [m + 1, r]

		// go to [l, m] | add m + 1 -> r to the suffix ST
		D.init(N);
		for(int x = m + 1; x <= r; x++) D.unite(E[x][1], E[x][2], E[x][0]);
		for(auto& e : S.bk.took) {
			// cout << "SUFFIX EX: " << e[1] << " " << e[2] << " " << e[0] << endl;
			D.unite(e[1], e[2], e[0]);
			if (sz(D.took) == N - 1) break;
		}

		S.pb(D); dnc(l, m); S.pop_back();


		// go to [m + 1, r] | add m -> l to the prefix ST
		D.init(N);
		for(int x = m; x >= l; x--) D.unite(E[x][1], E[x][2], E[x][0]);
		for(auto& e : P.bk.took) {
			// cout << "PREFIX EX: " << e[1] << " " << e[2] << " " << e[0] << endl;
			D.unite(e[1], e[2], e[0]);
			if (sz(D.took) == N - 1) break;
		}

		P.pb(D); dnc(m + 1, r); P.pop_back();
	};

	dnc(0, M - 1);

	for(auto& x : ANS) cout << x << nl;

	exit(0-0);
}

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