Submission #1142340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142340		NK_	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1105 ms	18236 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 int INF = 1e9 + 1008;

struct DSU {
	int N; vi e; void init(int n) { N = n; e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool same(int x, int y) { return get(x) == get(y); }
	bool unite(int rx, int ry) {
		rx = get(rx), ry = get(ry);
		if (rx == ry) return 0;
		// cout << "ADDED: " << x << " " << y << " => " << w << endl;
		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<T> add; DSU D;
	for(int i = 0; i < M; i++) {
		auto [w, u, v] = E[i];

		int l = i - 1, r = i + 1;
		D.init(N); while(l >= 0) {
			D.unite(E[l][1], E[l][2]); 
			if (D.same(u, v)) break;
			--l;
		}

		D.init(N); while(r < M) {
			D.unite(E[r][1], E[r][2]); 
			if (D.same(u, v)) break;
			++r;
		}

		int L = l < 0 ? -1 : (E[l][0] + w + 1) / 2;
		int R = r >= M ? INF : (w + E[r][0] + 1) / 2;

		// cout << i << " -> " << L << " " << R << endl;


		add.pb(T{L, -1, w});
		add.pb(T{w, +2, -2 * w});
		add.pb(T{R, -1, w});
	}


	sort(begin(add), end(add));


	int Q; cin >> Q;

	ll a = 0, b = 0;
	for(int q = 0, i = 0; q < Q; q++) {
		int x; cin >> x;

		while(i < sz(add) && add[i][0] <= x) {
			a += add[i][1];
			b += add[i][2];
			++i;
		}

		// cout << i << " " << q << " -> " << a << " " << b << endl;

		cout << a * 1LL * x + b << nl;
	}

	exit(0-0);
}

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