Submission #633980

#	Time	Username	Problem	Language	Result	Execution time	Memory
633980		S920105123	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1354 ms	41380 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 LL INF = (LL) 1e9 + 8763;
using namespace std;

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

struct DSU {
	int pa[MAXN], sz[MAXN];
	void init(int n) {
		for (int i = 0; i <= n; i++) {
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		return x == pa[x] ? x : pa[x] = find(pa[x]);
	}
	int merge(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return 0;
		if (sz[x] < sz[y]) swap(x, y);
		sz[x] += sz[y];
		pa[y] = x;
		return 1;
	}
} D;

int n, m;
Edge E[MAXM];

int qn;
vector<int> X;

void compute(vector<int> &L, vector<int> &R) {
	L.resize(m);
	R.resize(m);
	for (int i = 0; i < m; i++) {
		L[i] = i;
		R[i] = m - i - 1;
	}
	vector<int> prev_tree;
	for (int i = 0; i < m; i++) {
		vector<int> cur_tree(1, i);
		D.init(n);
		D.merge(E[i].u, E[i].v);
		for (int id : prev_tree) {
			if (D.find(E[id].u) == D.find(E[id].v)) {
				L[i] = R[id] = i - id - 1;
				continue;
			}
			D.merge(E[id].u, E[id].v);
			cur_tree.push_back(id);
		}
		prev_tree = move(cur_tree);
	}
}

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

	cin >> n >> m;
	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, R;
	compute(L, 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;
		}
		
		if (wl <= wr) {
			int pl = lower_bound(all_of(X), wl) - X.begin();
			int pm = lower_bound(all_of(X), max(E[i].w, wl)) - X.begin();
			int pr = upper_bound(all_of(X), wr) - X.begin();
			ev.push_back(PII(pl, i));
			ev.push_back(PII(pm, i));
			ev.push_back(PII(pr, i));
		}
	}
	
	// sweep
	int ptr = 0, neg = 0, pos = 0;
	LL cur = 0;
	vector<int> state(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 (state[id] == 0) {
				// insert
				state[id] = 1;
				neg++;
				cur += E[id].w;
			}
			else if (state[id] == 1) {
				// change
				state[id] = 2;
				neg--;
				pos++;
				cur -= 2 * E[id].w;
			}
			else {
				// remove
				pos--;
				state[id] = 3;
				cur += E[id].w;
			}
			ptr++;
		}
		
		// calc
		assert(pos + neg == n - 1);
		ans[i] = cur + (LL)pos * X[i] - (LL)neg * X[i];
	}
	for (int i = 0; i < qn; i++) {
		cout << ans[i] << '\n';
	}
}

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