Submission #911095

#	Time	Username	Problem	Language	Result	Execution time	Memory
911095		ParsaS	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1593 ms	69480 KiB

reconstruction

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;

const int N = 1e6 + 5;
int n, m, q;
vector<pair<int, pair<int, int> > > E;
int lt[N], rt[N], par[N], sz[N];
pair<int, int> qr[N];
ll ps[N], c[N], ans[N];

int get(int v) {
	return v == par[v] ? v : par[v] = get(par[v]);
}

void unite(int v, int u) {
	v = get(v), u = get(u);
	if (v == u)
		return;
	if (sz[v] > sz[u])
		swap(v, u);
	par[v] = u;
	sz[u] = sz[v] + sz[u];
}

void reset() {
	for (int i = 1; i <= n; i++)
		par[i] = i, sz[i] = 1;
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int v, u, w; cin >> v >> u >> w;
		E.pb(mp(w, mp(v, u)));
	}
	sort(E.begin(), E.end());
	for (int i = 0; i < m; i++) {
		reset();
		for (int j = i - 1; j >= 0; j--) {
			unite(E[j].se.fi, E[j].se.se);
			if (get(E[i].se.fi) == get(E[i].se.se)) {
				lt[i] = (E[i].fi + E[j].fi + 1) / 2;
				break;
			}
		}
		reset();
		rt[i] = 1e9 + 10;
		for (int j = i + 1; j < m; j++) {
			unite(E[j].se.fi, E[j].se.se);
			if (get(E[i].se.fi) == get(E[i].se.se)) {
				rt[i] = (E[i].fi + E[j].fi) / 2 - (E[i].fi + E[j].fi + 1) % 2;
				break;
			}
		}
		//cout << E[i].se.fi << ' ' << E[i].se.se << ' ' << E[i].fi << " : " << lt[i] << ' ' << rt[i] << endl;
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		qr[i] = mp(x, i);
	}
	sort(qr, qr + q);
	
	for (int i = 0; i < m; i++) {
		int l = lower_bound(qr, qr + q, mp(lt[i], 0)) - qr;
		int r = upper_bound(qr, qr + q, mp(rt[i], (int)1e9)) - qr;
		int cur = lower_bound(qr, qr + q, mp(E[i].fi, 0)) - qr;

		int w = E[i].fi;
		ps[l] += w;
		ps[cur] -= w + w;
		ps[r] += w;

		c[cur]++;
		c[r]--;
	}
	for (int i = 0; i < q; i++) {
		if (i) {
			ps[i] += ps[i - 1];
			c[i] += c[i - 1];
		}

		int x = qr[i].fi, j = qr[i].se;
		ans[j] = 1ll * x * (2 * c[i] - (n - 1)) + ps[i];
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 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