Submission #781065

#	Time	Username	Problem	Language	Result	Execution time	Memory
781065		aZvezda	Reconstruction Project (JOI22_reconstruction)	C++14	70 / 100	5081 ms	401496 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif

const ll MAX_N = 2e5 + 10; 
ll n, m;
pair<ll, pair<ll, ll> > edg[MAX_N];

struct {
	ll par[MAX_N], sz[MAX_N];
	vector<ll> now;

	void reset() {
		for(ll i = 1; i <= n; i ++) {
			par[i] = i;
			sz[i] = 1;
		}
		now.resize(0);
	}

	ll find(ll x) {
		if(par[x] == x) {
			return x;
		} else {
			return par[x] = find(par[x]);
		}
	}

	bool merge(ll x, ll y, ll c) {
		x = find(x); y = find(y);
		if(x == y) { return false; }
		if(sz[x] < sz[y]) { swap(x, y); }
		par[y] = x;
		sz[x] += sz[y];
		now.push_back(c);
		return true;
	}
} dsu;

vector<ll> cand[MAX_N];
ll lft[MAX_N], rght[MAX_N];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;
	for(ll i = 0; i < m; i ++) {
		cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first;
	}
	sort(edg, edg + m);

	dsu.reset();
	for(ll i = 0; i < m; i ++) {
		int other = -1;
		dsu.reset();
		dsu.merge(edg[i].second.first, edg[i].second.second, i);
		if(i != 0) for(const auto j : cand[i - 1]) {
			if(!dsu.merge(edg[j].second.first, edg[j].second.second, j)) {
				other = j;
			}
		}
		cand[i] = dsu.now;
		if(other != -1) {
			lft[i] = (edg[i].first + edg[other].first + 2ll) / 2ll;
			rght[other] = (edg[i].first + edg[other].first) / 2ll;
		} else {
			lft[i] = -1e12;
		}
		rght[i] = 1e12;
	}

	ll q;
	cin >> q;
	while(q --) {
		ll x;
		cin >> x;
		ll ans = 0;
		for(int i = 0; i < m; i ++) {
			if(lft[i] <= x && x <= rght[i]) {
				ans += abs(x - edg[i].first);
			}
		}
		cout << ans << endl;
	}
}

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