제출 #633499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633499		S920105123	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	3755 ms	148064 KiB

reconstruction

//#pragma GCC optimize ("O3", "unroll-loops")
//#pragma GCC target ("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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];
int vis[MAXN];
PII parent[MAXN];
vector<PII> G[MAXN];
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);
		}
	}
}

vector<Edge> trim(vector<Edge> es) {
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
		G[i].clear();
		parent[i] = PII(-1, -1);
	}
	for (Edge e : es) {
		G[e.u].push_back(PII(e.v, e.w));
		G[e.v].push_back(PII(e.u, e.w));
	}
	function<void(int)> dfs = [&] (int v) {
		vis[v] = 1;
		for (PII p : G[v]) {
			if (!vis[p.fi]) {
				dfs(p.fi);
				parent[p.fi] = PII(v, p.se);
			}
		}
	};
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	vector<Edge> res;
	for (int i = 1; i <= n; i++) {
		if (parent[i].fi != -1) {
			res.push_back((Edge){i, parent[i].fi, parent[i].se});
		}
	}
	return res;
}

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];
	}
	
	// trim useless edges
	int lp = 0, sz = 0;
	vector<Edge> temp = vector<Edge>(E, E + m);
	while (lp < m) {
		int rp = lp + 1;
		while (temp[rp].w == temp[lp].w) {
			rp++;
		}
		vector<Edge> F = trim(vector<Edge>(temp.begin() + lp, temp.begin() + rp));
		for (Edge e : F) {
			E[sz++] = e;
		}
		lp = rp;
	}
//	cout << "Trim " << m - sz << '\n';
	m = sz;
	
	// compute
	vector<int> L(m), R(m);
	compute(L);
	reverse(E, E + m);
	compute(R);
	reverse(E, E + m);
	reverse(all_of(R));
//	cout << "Edge:\n";
//	for (int i = 0; i < m; i++) {
//		cout << E[i].u << ' ' << E[i].v << " " << E[i].w << '\n';
//	}
//	cout << "\n\nLR:\n";
//	for (int i = 0; i < m; i++) {
//		cout << L[i] << ' ' << R[i] << '\n';
//	}
		
	// 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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:246:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |   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:5:
reconstruction.cpp:255:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  255 |   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