제출 #1190518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190518		JooDdae	도로 개발 (JOI15_road_development)	C++20	100 / 100	315 ms	21428 KiB

road_development

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

int n, m, p[100100];
vector<int> v[100100];

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int merge(int x, int y) { return (x = find(x)) == (y = find(y)) ? 0 : !!(p[x] = y); }

int sz[100100], head[100100], par[100100], in[100100], lev[100100], cnt;

int dfs_sz(int u, int p) {
	sz[u] = 1, par[u] = p, lev[u] = lev[p]+1;
	if(p) v[u].erase(find(v[u].begin(), v[u].end(), p));
	for(auto &x : v[u]) {
		sz[u] += dfs_sz(x, u);
		if(sz[x] > sz[v[u][0]]) swap(x, v[u][0]);
	}
	return sz[u];
}

void dfs_hld(int u) {
	in[u] = ++cnt;
	for(auto x : v[u]) {
		head[x] = (x == v[u][0] ? head[u] : x);
		dfs_hld(x);
	}
}

int t[400400];
bool d[400400];

int build(int node = 1, int l = 1, int r = n) {
	if(l == r) return t[node] = 1;
	return t[node] = build(node*2, l, mid) + build(node*2+1, mid+1, r);
}

int update(int nl, int nr, int node = 1, int l = 1, int r = n) {
	if(nr < l || r < nl || d[node]) return 0;
	if(nl <= l && r <= nr) return d[node] = 1, t[node] = 0;
	update(nl, nr, node*2, l, mid), update(nl, nr, node*2+1, mid+1, r);
	return t[node] = t[node*2] + t[node*2+1];
}

int query(int nl, int nr, int node = 1, int l = 1, int r = n) {
	if(nr < l || r < nl || d[node]) return 0;
	if(nl <= l && r <= nr) return t[node];
	return query(nl, nr, node*2, l, mid) + query(nl, nr, node*2+1, mid+1, r);
}

int hld(int x, int y, bool up) {
	int re = 0;
	while(head[x] != head[y]) {
		if(lev[head[x]] < lev[head[y]]) swap(x, y);
		re += (up ? update : query)(in[head[x]], in[x], 1, 1, n);
		x = par[head[x]];
	}
	if(in[x] > in[y]) swap(x, y);
	if(x != y) re += (up ? update : query)(in[x]+1, in[y], 1, 1, n);
	return re;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	vector<array<int, 3>> q(m);
	iota(p+1, p+1+n, 1);
	for(auto &[t, x, y] : q) {
		cin >> t >> x >> y;
		if(t == 1 && merge(x, y)) v[x].push_back(y), v[y].push_back(x);
	}

	for(int i=1;i<=n;i++) if(!in[i]) dfs_sz(i, 0), dfs_hld(i);
	build(), iota(p+1, p+1+n, 1);

	for(auto &[t, x, y] : q) {
		if(t == 1) {
			if(!merge(x, y)) hld(x, y, 1);
		} else {
			cout << (find(x) == find(y) ? hld(x, y, 0) : -1) << "\n";
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15