글 읽기 - 런타임에러 지옥에서 벗어나질 못하겠습니다. 제발 도와주세요.

zizon233 5년 전 0

살려주세요.

a, b가 다를경우 밑에서부터 올라가는 걸로 소스 짰습니다.

조상 노드 저장하는것도 조금 특이할 수 있습니다.

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	int n, m, deep = 1, parents[19][100001] = { 0 }, visited[100001] = { 0 }, depth[100001] = { 0 }, k = 1, check = 2;
	vector arr[100001];
	queue bfs;
	cin >> n;
	for (int i = 1; i < n; i++) { //입력
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	bfs.push(1);
	visited[1] = 1;
	while (!bfs.empty()) { //bfs로 깊이 부모저장
		int temp = bfs.size();
		for (int i = 0; i < temp; i++) {
			for (int j = 0; j < arr[bfs.front()].size(); j++) {
				if (!visited[arr[bfs.front()][j]]) {
					bfs.push(arr[bfs.front()][j]);
					visited[arr[bfs.front()][j]] = 1;
					parents[0][arr[bfs.front()][j]] = bfs.front();
					depth[arr[bfs.front()][j]] = deep;
				}
			}
			bfs.pop();
		}
		deep++;
	}
	while (true) { //조상전부저장
		for (int i = n; i >= 1; i--) {
			parents[k][i] = parents[k - 1][parents[k - 1][i]];
		}
		k++;
		check <<= 1;
		if (check>deep) break;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (depth[a] > depth[b]) { // 깊이 맞춰줌
			int temp = depth[a] - depth[b];
			k = 1;
			while (temp > 0) {
				if (temp % 2 == 1) {
					a = parents[k - 1][a];
				}
				k <<= 1;
				temp /= 2;
			}
		}
		else if (depth[a] < depth[b]) {
			int temp = depth[b] - depth[a];
			k = 1;
			while (temp > 0) {
				if (temp % 2 == 1) {
					b = parents[k - 1][b];
				}
				k <<= 1;
				temp /= 2;
			}
		}
		if (a != b) { // 깊이가 같지만 값이 다를경우
			k = 0;
			while (true) {
				while (parents[k][a] != parents[k][b]) {
					k++;
				}
				if (k == 0) {
					a = parents[k][a];
					b = parents[k][b];
					break;
				}
				else {
					a = parents[k - 1][a];
					b = parents[k - 1][b];
				}
				k = 0;
			}
		}
		cout << a << '\n';
	}
	return 0;
}

seico75 5년 전 1

이런 예제는 어떨까요?

이진 균형트리를 가정하고 19로 최대 depth 를 정하신 것 같습니다.

zizon233 5년 전 0

깊이는 2의 승수로 2의 18승은 1000000을 넘는 것으로 계산기로 확인했어요ㅠㅠ

zizon233 5년 전 0

님 천재신가요. 제가 k를 왜 시프트를 줬는지 모르겠군요. 정신이 나갔었나봐요.

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

문제

문제

출처

ICPC

런타임에러 지옥에서 벗어나질 못하겠습니다. 제발 도와주세요.

zizon233 5년 전 0

seico75 5년 전 1

zizon233 5년 전 0

zizon233 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말