Submission #587042

#	Time	Username	Problem	Language	Result	Execution time	Memory
587042		8e7	Reconstruction Project (JOI22_reconstruction)	C++17	35 / 100	5067 ms	57136 KiB

reconstruction

//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 505
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};

struct DSU{
	int par[maxn], siz[maxn];	
	void init(int n) {
		for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (siz[a] < siz[b]) par[a] = b;
		else par[b] = a;
		return 1;
	}
} dsu;
vector<edge> ed;
vector<int> wei;
int n, m;
vector<int> se(int x) {
	int st = lower_bound(wei.begin(), wei.end(), x) - wei.begin();
	int l = st-1;
	dsu.init(n);
	vector<int> ret;
	for (;st < m;st++) {
		while (l >= 0 && x - wei[l] <= wei[st] - x) {
			if (dsu.Union(ed[l].u, ed[l].v)) ret.push_back(l);
			l--;
		}
		if (dsu.Union(ed[st].u, ed[st].v)) ret.push_back(st);
	}
	while (l >= 0) {
		if (dsu.Union(ed[l].u, ed[l].v)) ret.push_back(l);
		l--;
	}
	sort(ret.begin(), ret.end());
	/*
	debug(x);
	pary(ret.begin(), ret.end());
	debug();
	*/
	return ret;
}
ll ans[1000005];

void solve(vector<pii> v) {
	if (v.size() == 0) return;
	if (v.size() == 1) {
		vector<int> e = se(v[0].ff);
		for (int i:e) ans[v[0].ss] += abs(wei[i] - v[0].ff);
		return;
	}
	vector<int> e = se(v[0].ff);
	if (e == se(v.back().ff)) {
		for (pii p:v) {
			for (int i:e) ans[p.ss] += abs(wei[i] - p.ff);
		}
		return;
	}
	vector<pii> lef(v.begin(), v.begin() + (v.size() / 2));
	vector<pii> rig(v.begin() + (v.size()/2), v.end());
	solve(lef);
	solve(rig);
}
int main() {
	io
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed.push_back(edge(u, v, w));
		wei.push_back(w);
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	sort(wei.begin(), wei.end());

	int q;
	cin >> q;
	vector<pii> que(q);
	for (int i = 0;i < q;i++) {
		cin >> que[i].ff;
		que[i].ss = i;
	}
	solve(que);
	for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}

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