Submission #1151413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151413		beaboss	Reconstruction Project (JOI22_reconstruction)	C++20	42 / 100	1014 ms	429544 KiB

reconstruction

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }


class DisjollSets {
  private:
	vector<ll> parents;
	vector<ll> sizes;

  public:
	DisjollSets(ll size) : parents(size), sizes(size, 1) {
		for (ll i = 0; i < size; i++) { parents[i] = i; }
	}

	/** @return the "representative" node in x's component */
	ll find(ll x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

	/** @return whether the merge changed connectivity */
	bool unite(ll x, ll y) {
		ll x_root = find(x);
		ll y_root = find(y);
		if (x_root == y_root) { return false; }

		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}

	/** @return whether x and y are in the same connected component */
	bool connected(ll x, ll y) { return find(x) == find(y); }
};

const ll N = 1e5 + 10;
const ll INF = 1e9 + 10;
map<ll, vpii> byw;
vpii q;
ll res[N];

vector<array<ll ,3> > ri[N], le[N];

ll n;
void solve(ll l, ll r) {
	if (r - l == 1) return;
	// cout << l <<r << endl;
	ll m = (l + r)/2;
	ll here = q[m].f;
	ll ind = q[m].s;
	vector<array<ll, 3> > edges;
	// from before
	for (auto val: le[l])
		edges.pb(val);

	// from after
	for (auto val: ri[r])
		edges.pb(val);
	
	for (auto it = byw.upper_bound(q[l].f); it != byw.end() && (*it).f < q[r].f; it++) {
		for (auto e: it->s) edges.pb({e.f, e.s, (*it).f});
	}

	vector<array<ll, 4> > ne_edges(edges.size());
	FOR(i, 0, edges.size()) {

		ne_edges[i] = {abs(here - edges[i][2]), edges[i][0], edges[i][1], edges[i][2]};
	}

	DisjollSets dsu(n + 1);

	sort(ne_edges.begin(), ne_edges.end());
	for (auto e: ne_edges) {
		// cout << e[1] << e[2] << endl;
		if (dsu.unite(e[1], e[2])) {
			res[ind] += e[0];
			if (e[3] >= here) ri[m].pb({e[1], e[2], e[3]});
			if (e[3] <= here) le[m].pb({e[1], e[2], e[3]});
		}
	}

	solve(l, m);solve(m, r);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll m;
	cin >> n >> m;

	FOR(i, 0, m) {
		ll x, y, w;
		cin >> x >> y >> w;
		byw[w].pb({x, y});
	}

	ll qq;
	cin >> qq;
	q.push_back({-1, 0});
	FOR(_, 0, qq) {
		ll a;
		cin >> a;
		q.pb({a, _});
	}
	q.push_back({INF, 0});
	sort(q.begin(), q.end());

	solve(0, q.size()-1);
	FOR(_, 0, qq) cout << res[_] << endl;
}

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