Submission #721434

#	Time	Username	Problem	Language	Result	Execution time	Memory
721434		Abrar_Al_Samit	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5055 ms	4464 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;

const int nax = 503;
const int bnax = 1e6 + 3;

int n, m;
long long ans[bnax];
vector<tuple<int,int,int>>edges;

struct DSU {
	int dad[nax], sz[nax];

	void reset() {
		for(int i=1; i<nax; ++i) {
			dad[i] = i, sz[i] = 1;
		}
	}
	int find(int v) {
		return dad[v] = (v==dad[v]) ? v : find(dad[v]);
	}
	void unite(int u, int v) {
		u = find(u), v = find(v);
		if(sz[u] < sz[v]) swap(u, v);
		dad[v] = u;
		sz[u] += sz[v];
	}
	bool same(int u, int v) {
		return find(u) == find(v);
	}
} T;
long long MakeTree(int x, long long &cnt1, long long &cnt2) {
	long long ret = 0;
	sort(edges.begin(), edges.end(), [&] (auto p, auto q) {
		auto [w1, u1, v1] = p;
		auto [w2, u2, v2] = q;
		return abs(x-w1) < abs(x-w2);
	});

	T.reset();
	cnt1 = cnt2 = 0;
	for(auto [w, u, v] : edges) {
		if(!T.same(u, v)) {
			T.unite(u, v);
			if(x >= w) ++cnt1;
			else ++cnt2;
			ret += abs(x-w);
		}
	}
	return ret;
}
void PlayGround() {
	cin>>n>>m;
	edges.resize(m);
	for(auto &[w, u, v] : edges) {
		cin>>u>>v>>w;
	}
	int q;
	cin>>q;
	while(q--) {
		long long z;
		int x;
		cin>>x;
		cout<<MakeTree(x, z, z)<<'\n';
	}


	// sort(edges.begin(), edges.end());
	// set<int>makeTree = {get<0>(edges[0])};

	// vector<int>points = {get<0>(edges[0])};
	// for(int i=1; i<m; ++i) {
	// 	auto [w1, u1, v1] = edges[i-1];
	// 	auto [w2, u2, v2] = edges[i];
	// 	makeTree.insert((w1+w2+1)/2);
	// 	points.push_back((w1+w2+1)/2);

	// 	points.push_back(w2);
	// 	makeTree.insert(w2);
	// }

	// int q;
	// cin>>q;
	// vector<pair<int,int>>qs(q);
	// for(int i=0; i<q; ++i) {
	// 	int x;
	// 	cin>>x;
	// 	qs[i] = {x, i};
	// 	points.push_back(x);
	// }
	// sort(qs.begin(), qs.end());
	// sort(points.begin(), points.end());
	// points.resize(unique(points.begin(), points.end()) - points.begin());

	// int at = 0;
	// long long cnt1, cnt2;

	// long long cur = 0;
	// int prv;

	// // cerr<<MakeTree(14, cnt1, cnt2)<<'\n';
	// // cerr<<cnt1<<' '<<cnt2<<'\n';
	// // exit(0);
	// for(int x : points) {
	// 	if(makeTree.count(x)) {
	// 		cur = MakeTree(x, cnt1, cnt2);
	// 	} else {
	// 		cur += cnt1 * (x-prv) - cnt2 * (x-prv);
	// 	}
	// 	auto [z, j] = qs[at];
	// 	if(z==x) {
	// 		ans[j] = cur;
	// 		++at;
	// 		if(at==q) break;
	// 	}
	// 	prv = x;
	// }
	// for(int i=0; i<q; ++i) {
	// 	cout<<ans[i]<<'\n';
	// }

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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