Submission #633520

#	Time	Username	Problem	Language	Result	Execution time	Memory
633520		S920105123	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	3239 ms	142928 KiB

reconstruction

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define all_of(v) (v).begin(), (v).end()
#define fi first
#define se second
const int MAXM = 100005;
const int MAXN = 505;
const int SIZE = 400;
const LL INF = (LL) 1e9 + 8763;
using namespace std;

struct Edge {
	int u, v;
	LL w;
};

struct DSU {
	// 1-based roll-back DSU
	struct Record {
		int x, y; // y is merged into x
	};
	int pa[MAXN], sz[MAXN];
	vector<Record> stk;
	void init(int n) {
		stk.clear();
		for (int i = 1; i <= n; i++) {
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		return x == pa[x] ? x : find(pa[x]);
	}
	int merge(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) {
			stk.push_back((Record){-1, -1});
			return 0;
		}
		if (sz[x] < sz[y]) swap(x, y);
		sz[x] += sz[y];
		pa[y] = x;
		stk.push_back((Record){x, y});
		return 1;
	}
	int same(int x, int y) {
		return find(x) == find(y);
	}
	void roll_back() {
		assert(!stk.empty());
		Record r = stk.back();
		stk.pop_back();
		if (r.x != -1) {
			pa[r.y] = r.y;
			sz[r.x] -= sz[r.y];
		}
	}
};

int n, m, sq;
Edge E[MAXM];
DSU D[MAXM / SIZE + 5];

int qn;
vector<int> X;

void compute(vector<int> &res) {
	int cnt = 0, pseudo = MAXM / SIZE + 4;
	D[pseudo].init(n);
	for (int i = 0; i < m; i++) {
		// stage 1
		int j, pre = i, last = pseudo;
		for (j = cnt - 1; j >= 0; j--) {
			if (D[j].same(E[i].u, E[i].v)) {
				break;
			}
			pre = j * SIZE;
			last = j;
		}
		
		// stage 2
		int op = 0;
		while (pre > 0) {
			op++;
			D[last].merge(E[pre - 1].u, E[pre - 1].v);
			if (D[last].same(E[i].u, E[i].v)) {
				break;
			}
			pre--;
		}
		res[i] = i - pre;
		for (int i = 0; i < op; i++) {
			D[last].roll_back();
		}
		
		// add E[i];
		if (i % SIZE == 0) {
			D[cnt++].init(n);
		}
		for (int j = 0; j < cnt; j++) {
			D[j].merge(E[i].u, E[i].v);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;
	sq = (int)(sqrt(m) + 0.5);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		E[i] = (Edge){u, v, w};
	}
	sort(E, E + m, [&] (Edge e1, Edge e2) {
		return e1.w < e2.w;
	});
	cin >> qn;
	X.resize(qn);
	for (int i = 0; i < qn; i++) {
		cin >> X[i];
	}
		
	// compute
	vector<int> L(m), R(m);
	compute(L);
	reverse(E, E + m);
	compute(R);
	reverse(E, E + m);
	reverse(all_of(R));
		
	// make answer
	vector<PII> ev;
	for (int i = 0; i < m; i++) {
		int l = i - L[i] - 1, r = i + R[i] + 1, wl, wr;
		if (l < 0) {
			wl = -INF;
		}
		else {
			wl = (E[i].w + E[l].w) / 2 + 1;
		}
		if (r >= m) {
			wr = INF;
		}
		else {
			wr = (E[i].w + E[r].w) / 2;
		}
		
		int pl = lower_bound(all_of(X), wl) - X.begin();
		int pr = upper_bound(all_of(X), wr) - X.begin();
		ev.push_back(PII(pl, ~i));
		ev.push_back(PII(pr, i));
	}
	
	// sweep
	int ptr = 0;
	vector<int> all, active(m);
	vector<LL> ans(qn, 0);
	sort(all_of(ev));
	for (int i = 0; i < qn; i++) {
		while (ev[ptr].fi <= i) {
			int id = ev[ptr].se;
			if (ev[ptr].se < 0) {
				// insert
				id = ~id;
				assert(active[id] == 0);
				active[id] = 1;
				all.push_back(id);
			}
			else {
				assert(active[id] == 1);
				active[id] = 0;
			}
			ptr++;
		}
		
		// calc
		int j = 0;
		while (j < all.size()) {
			if (!active[all[j]]) {
				swap(all[j], all.back());
				all.pop_back();
				continue;
			}
			ans[i] += abs(E[all[j]].w - X[i]);
			j++;
		}
		assert(all.size() == n - 1);
	}
	for (int i = 0; i < qn; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:181:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |   while (j < all.size()) {
      |          ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from reconstruction.cpp:1:
reconstruction.cpp:190:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  190 |   assert(all.size() == n - 1);
      |          ~~~~~~~~~~~^~~~~~~~

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