Submission #587798

#	Time	Username	Problem	Language	Result	Execution time	Memory
587798		8e7	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	920 ms	1048576 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 maxm 100005
#define maxq 1000005
#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, id;
	edge(){u = v = w = id = 0;}
	edge(int a, int b, int c, int d){u = a, v = b, w = c, id = d;}
};

struct DSU{
	int par[maxn], siz[maxn];	
	vector<pii> op;
	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 : (find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) {
			op.push_back({0, 0});
			return 0;
		}
		if (siz[a] < siz[b]) swap(a, b);
		siz[a] += siz[b];
		par[b] = a;
		op.push_back({a, b});
		return 1;
	}
	void undo(int x) {
		while (x--) {
			assert(op.size() > 0);	
			int a = op.back().ff, b = op.back().ss;
			if (a) {
				siz[a] -= siz[b];
				par[b] = b;
			}
			op.pop_back();
		}
	}
} dsu;
vector<int> wei;
pii ran[maxm];

void solve(int l, int r, vector<edge> ed, vector<edge> lef, vector<edge> rig) {
	int m = (l + r) / 2;
	vector<edge> el, er, l0, r0, e1, l1, r1;

	int tot = ed.size() + lef.size() + rig.size();
	if (tot == 0) return;
	/*
	debug(l, r);
	for (auto e:ed) debug(e.id);
	debug();
	for (auto e:lef) debug(e.id);
	debug();
	for (auto e:rig) debug(e.id);
	debug("pick");
	*/

	auto cmp = [&] (edge &x, edge &y){
		return abs(x.w - m) < abs(y.w - m);
	};
	sort(ed.begin(), ed.end(), cmp);
	sort(lef.begin(), lef.end(), cmp);
	sort(rig.begin(), rig.end(), cmp);
	int s0 = ed.size(), s1 = lef.size(), s2 = rig.size();
	int i0 = 0, i1 = 0, i2 = 0;	
	for (int tmp = 0;tmp < tot;tmp++) {
		int mi = (i0 < s0 ? 0 : (i1 < s1 ? 1 : 2));
		edge cur = i0 < s0 ? ed[i0] : (i1 < s1 ? lef[i1] : rig[i2]);	
		if (i1 < s1 && cmp(lef[i1], cur)) {
			cur = lef[i1], mi = 1;
		}
		if (i2 < s2 && cmp(rig[i2], cur)) {
			cur = rig[i2], mi = 2;
		}
		if (mi == 0) {
			i0++;
			if (dsu.Union(cur.u, cur.v)) e1.push_back(cur);
			else if (cur.w < m) el.push_back(cur);
			else er.push_back(cur);
		} else if (mi == 1) {
			i1++;
			if (dsu.Union(cur.u, cur.v)) l1.push_back(cur);
			else l0.push_back(cur);
		} else {
			i2++;
			if (dsu.Union(cur.u, cur.v)) r1.push_back(cur);
			else r0.push_back(cur);
		}
	}
	dsu.undo(tot);

	for (auto e:e1) ran[e.id] = {m, m+1};
	for (auto e:l1) ran[e.id].ff = m;
	for (auto e:l0) ran[e.id].ff = r;
	for (auto e:r1) ran[e.id].ss = m+1;
	for (auto e:r0) ran[e.id].ss = l;
	if (r - l == 1) return;

	vector<edge> tr = r1, tl = l1;
	tr.insert(tr.end(), e1.begin(), e1.end());
	tl.insert(tl.end(), e1.begin(), e1.end());

	int cnt = l1.size();
	for (auto e:l1) dsu.Union(e.u, e.v);
	solve(m+1, r, er, l0, tr);
	dsu.undo(cnt);
	
	cnt = r1.size();
	for (auto e:r1) dsu.Union(e.u, e.v);
	solve(l, m+1, el, tl, r0);
	dsu.undo(cnt);
}
bool on[maxm];
int main() {
	io
	int n, m;
	cin >> n >> m;
	vector<edge> ed, inil, inir;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		wei.push_back(w);
		ed.push_back(edge(u, v, w, i));	
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	for (int i = 0;i < m;i++) ed[i].id = i;
	sort(wei.begin(), wei.end());
	dsu.init(n);
	solve(1, inf, ed, inil, inir);

	vector<pii> ev;
	for (int i = 0;i < m;i++) {
		//debug(ed[i].u, ed[i].v, ed[i].w, ran[i].ff, ran[i].ss);
		if (ran[i].ff) {
			ev.push_back({ran[i].ff, i});
			ev.push_back({ran[i].ss, i});
		}
	}
	sort(ev.begin(), ev.end());
 
	int q;
	cin >> q;
	vector<int> que(q);
	multiset<int> se;

	int ind = 0;
	for (int i = 0;i < q;i++) {
		cin >> que[i];
		while (ind < ev.size() && ev[ind].ff <= que[i]) {
			if (!on[ev[ind].ss]) {
				se.insert(wei[ev[ind].ss]);
				on[ev[ind].ss] = 1;
			} else {
				se.erase(se.find(wei[ev[ind].ss]));
			}
			ind++;
		}
		ll ans = 0;
		for (int j:se) ans += abs(j - que[i]);
		cout << ans << "\n";
	}
	//for (int i = m - 1;i >= 0;i--) debug(ed[i].u, ed[i].v, ed[i].w);
 
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:174:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   while (ind < ev.size() && ev[ind].ff <= que[i]) {
      |          ~~~~^~~~~~~~~~~

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