Submission #1151412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151412		beaboss	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	133 ms	24244 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<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

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

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

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


class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;

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

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

	/** @return whether the merge changed connectivity */
	bool unite(int x, int y) {
		int x_root = find(x);
		int 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(int x, int y) { return find(x) == find(y); }
};

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

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

int n;
void solve(int l, int r) {
	if (r - l == 1) return;
	// cout << l <<r << endl;
	int m = (l + r)/2;
	int here = q[m].f;
	int ind = q[m].s;
	vector<array<int, 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<int, 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]};
	}

	DisjointSets 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);
	int m;
	cin >> n >> m;

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

	int qq;
	cin >> qq;
	q.push_back({-1, 0});
	FOR(_, 0, qq) {
		int 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: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23