취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3351번 문제인 삼각 분할이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3351 

볼록다각형의 삼각분할이 주어질 때, 각 삼각형을 노드로 하고 변을 공유하는 삼각형들의 노드 사이에 에지를 그으면 그 그래프는 트리가 됨을 알 수 있다. (사이클이 존재한다면, 공유하는 하나의 꼭짓점이 존재하는 사이클이 존재하고 이는 볼록다각형의 꼭짓점만을 사용한 분할이 아니게 되기 때문이다.)

이 트리를 구현하고, 같은 색을 가진 꼭짓점 사이에 있는 에지를 모두 "자를 수 없는 에지"로 표시하여 문제를 해결할 수 있다. 글쓴이는 이를 HLD(heavy-light decomposition)와 지연전파(lazy propagation)를 이용한 세그먼트 트리(segment tree)로 해결하였다.

HLD를 이용하여 에지를 관리할 때 루트방향이 어느 쪽인지 혼동하는 실수를 줄여야하는데...

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> G[100001];
vector<int> colors[100001];
vector <pair<pair<int, int>, int>> edges;

int heavychild[100001];
int dfs(int current, int parent) {
	int childcnt = 1;
	int hchild = -1;
	int hcount = -1;
	for (auto node : G[current]) {
		if (node == parent) continue;
		int temp = dfs(node, current);
		childcnt += temp;
		if (temp > hcount) {
			hcount = temp;
			hchild = node;
		}
	}
	heavychild[current] = hchild;
	return childcnt;
}

int nodeidx[100001];
int chainidx[100001];
int cnth[100001];
int cparent[100001];
int cdepth[100001];

int nidx = 1, cidx = 1;
void hld(int current, int parent, int cn, int cp, int cd) {
	nodeidx[current] = nidx;
	chainidx[nidx] = cidx;
	cnth[nidx] = cn;
	cparent[nidx] = cp;
	cdepth[nidx] = cd;

	int hchild = heavychild[current];
	if (hchild > 0) {
		nidx++;
		hld(hchild, current, cn + 1, cp, cd);
	}
	cd++;
	for (auto node : G[current]) {
		if (node == parent || node == hchild) continue;
		nidx++; cidx++;
		hld(node, current, 0, nodeidx[current], cd);
	}
}

int seg[262145];
bool lazy[262145];

void propagate(int L, int R, int sI) {
	seg[sI] = (R - L + 1);
	if (L < R) {
		lazy[sI * 2] = 1;
		lazy[sI * 2 + 1] = 1;
	}
	lazy[sI] = 0;
}

int update(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]) propagate(L, R, sI);
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] = 1;
		propagate(L, R, sI);
		return seg[sI];
	}
	return seg[sI] = update(L, (L + R) / 2, qL, qR, sI * 2) + update((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

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

	int N; cin >> N;
	for (int i = 3; i <= N; i++) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		
		colors[d].push_back(i);

		if (a < b) edges.push_back({ {a,b},i });
		else edges.push_back({ {b,a},i });
		
		if (b < c) edges.push_back({ {b,c},i });
		else edges.push_back({ {c,b},i });
		
		if (c < a) edges.push_back({ {c,a},i });
		else edges.push_back({ {a,c},i });
	}
	sort(edges.begin(), edges.end());
	int esize = edges.size();
	for (int i = 1; i < esize; i++) {
		if ((edges[i - 1].first.first == edges[i].first.first) && (edges[i - 1].first.second == edges[i].first.second)) {
			int x = edges[i - 1].second, y = edges[i].second;
			G[x].push_back(y);
			G[y].push_back(x);
		}
	}

	dfs(N, 0);
	hld(N, 0, 0, 0, 0);

	for (int i = 1; i <= N; i++) {
		int cnt = colors[i].size();
		for (int k = 1; k < cnt; k++) {
			int x = nodeidx[colors[i][k - 1]], y = nodeidx[colors[i][k]];
			if (cdepth[x] != cdepth[y]) {
				if (cdepth[x] < cdepth[y]) swap(x, y);
				while (cdepth[x] > cdepth[y]) {
					update(1, N, x - cnth[x], x, 1);
					x = cparent[x];
				}
			}
			while (chainidx[x] != chainidx[y]) {
				update(1, N, x - cnth[x], x, 1);
				update(1, N, y - cnth[y], y, 1);
				x = cparent[x], y = cparent[y];
			}
			if (x > y) swap(x, y);
			if (x < y) update(1, N, x + 1, y, 1);
		}
	}

	cout << N - 3 - seg[1];
}