Submission #781069

#	Time	Username	Problem	Language	Result	Execution time	Memory
781069		aZvezda	Reconstruction Project (JOI22_reconstruction)	C++14	31 / 100	1351 ms	16036 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 = 2e3 + 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;
	}

	priority_queue<pair<ll, pair<ll, ll> > > pq;
	for(int i = 0; i < m; i ++) {
		pq.push({-lft[i], {-1, edg[i].first}});
		pq.push({-edg[i].first, {0, edg[i].first}});
		pq.push({-rght[i] - 1, {1, edg[i].first}});
	}

	ll cntadd = 0;
	ll cntrem = 0;
	ll sum = 0;

	ll q;
	cin >> q;
	while(q --) {
		ll x;
		cin >> x;
		while(!pq.empty() && -pq.top().first <= x) {
			auto curr = pq.top(); pq.pop();
			if(curr.second.first == -1) {
				cntadd ++;
				sum += curr.second.second;
			} else if(curr.second.first == 0) {
				cntadd --;
				cntrem ++;
				sum -= curr.second.second * 2ll;
			} else {
				cntrem --;
				sum += curr.second.second;
			}
		}
		ll ans = sum - cntadd * x + cntrem * x;
		cout << ans << endl;
	}
}

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