글 읽기 - 왜 틀렸을까요..ㅠㅠ

h0ngjun7 8년 전 0

아래에 제가 작성한 소스코드에 있습니다.

필요하다고 생각되는 부분들에 대해서는 주석을 달았습니다.

도움을 주시면 대단히 감사하겠습니다.

#include <stdio.h>
#include <map>
using namespace std;
const int K = 1010;
const int MAXN = 300005;
map <int, int> cd; //색이 0~10^9이라서 압축하기 위해.
int n, m, pa[MAXN], col[MAXN], chk[MAXN], cnt[MAXN], C;
//pa[i] = i번 노드의 부모
//col[i] = i번 노드와 i번 부모 노드를 잇는 간선의 색깔
//chk[i] = LCA를 찾는 과정에서 k번째 쿼리에 대해서 이미 i를 방문한 적이 있는지의 유무
//cnt[i] = 두 노드 사이의 색의 개수를 카운팅할 때, 해당 색을 k번째 쿼리에 대해 이미 카운팅했는지 유무
//k번째 쿼리에 대한 노드 a와 노드 b의 LCA 구하기
int par(int a, int  b, int k) {
	if (a == b) return a;
	chk[a] = chk[b] = k;
	for (int i = 1; pa[a] != -1 && i <= K; i++) {
		a = pa[a];
		chk[a] = k;
	}
	for (int i = 1; pa[b] != -1 && i <= K; i++) {
		b = pa[b];
		if (chk[b] == k) break;
	}
	return b;
}
int main() {
	scanf("%d%d", &n, &m);
	//0번 노드의 부모는 없고, 모든 정점과 그 정점의 부모를 잇는 간선의 색은 0번 색이다.
	pa[0] = -1; cd[0] = 1; C = 1;
	for (int k = 1; k <= m; k++) {
		int T, a, b, c;
		scanf("%d%d%d", &T, &a, &b);
		if (T == 1) {
			scanf("%d", &c);
			if (a == b) continue; //두 정점이 같으면 칠할 간선이 없음
			if (!cd[c]) cd[c] = ++C; //사용한 적이 없는 색이면, 새로운 색으로 등록
			c = cd[c] - 1; //renumbering된 색을 받음
			int p = par(a, b, k);
			while (a != p) col[a] = c, a = pa[a];
			while (b != p) col[b] = c, b = pa[b];
		}
		else if (T == 2) pa[a] = b;
		else {
			int p = par(a, b, k), count = 0;
			//k번째 쿼리에 대해서 해당 색을 쓴 적이 없으면, count++
			while (a != p) {
				if (cnt[col[a]] != k) cnt[col[a]] = k, count++;
				a = pa[a];
			}
			while (b != p) {
				if (cnt[col[b]] != k) cnt[col[b]] = k, count++;
				b = pa[b];
			}
			printf("%d\n", count);
		}
	}
}

h0ngjun7 8년 전 1

찾았습니당. par함수가 다음과 같이 바뀌어야되더군요.

a와 b의 LCA가 b인 경우 제대로 동작하지 않고 있었습니다.

int par(int a, int  b, int k) {
	if (a == b) return a;
	chk[a] = k;
	for (int i = 1; pa[a] != -1 && i <= K; i++) {
		a = pa[a];
		chk[a] = k;
	}
	if (chk[b] == k) return b;
	for (int i = 1; pa[b] != -1 && i <= K; i++) {
		b = pa[b];
		if (chk[b] == k) break;
	}
	return b;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸을까요..ㅠㅠ

h0ngjun7 8년 전 0

h0ngjun7 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말