글 읽기 - LCA 문제 4%에서 틀린 점 좀 찾아주실 수 있나요..?

his130 6년 전 0

LCA 2번 문제를 DP를 이용했습니다.

1.양방향 간선으로 입력받기

2.BFS 이용해서 루트가 1인 트리 만들기

3.LCA 알고리즘 이용하기

max_level 로 최대값 정해놓고, 줄여가면서

첫번째로 높이 맞추고

두번째로 같지 않은 곳까지 올라가서, 첫번째 부모 출력

같다면 그대로 출력하도록 했는데..어디서 문제일까요?

#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;

const int Max_Num = 10001;
const int max_level = (int)floor(log2(Max_Num));
int LCA(int a, int b, vector<vector<int>> &p,vector<int> &depth)
{
	//높이 맞추기

	if (depth[a] < depth[b])
	{
		swap(a, b);
	}

	if(depth[a] != depth[b])
	{
		for (int i = max_level; i >= 0; i--)
		{
			if (depth[p[a][i]] >= depth[b])
			{
				a = p[a][i];
			}
		}
	}

	if (a != b)
	{
		for (int i = max_level; i >= 0; i--)
		{
			if (p[a][i] != p[b][i])
			{
				a = p[a][i];
				b = p[b][i];
			}

		}

		return p[a][0];

	}
	else
	{
		return a;
	}

}

int main()
{
	//freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d", &n);
	vector<vector<int>> v(n + 1);
	vector<int> depth(n + 1, 0);
	vector<vector<int>> p(n + 1, vector<int>(max_level+1, 0));
	vector<int> ans;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}

	////////////////bfs로 트리만들기(루트가 1)

	queue<int> q;
	depth[1] = 1;
	q.push(1);

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < v[now].size(); i++)
		{
			int next = v[now][i];
			if (depth[next] == 0)
			{
				depth[next] = depth[now] + 1;
				//p초기화
				p[next][0] = now;
				q.push(next);
			}
		}
	}
	////////////////////////DP 채우기

	for (int j = 1; j <= max_level; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			if (p[i][j - 1] != 0)
			{
				p[i][j] = p[p[i][j - 1]][j - 1];
			}
		}
	}
    
    //입력받고 LCA 함수 돌리기
	scanf("%d", &m);
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		ans.push_back(LCA(a, b, p, depth));
	}


	for (int i = 0; i < ans.size(); i++)
	{
		printf("%d\n", ans[i]);
	}

	return 0;
}

ntopia 6년 전 1

입력 설명을 보면 N<=100000 이라고 되어있습니다.

Max_Num 을 더 크게 잡아야겠네요

his130 6년 전 0

아.. 제 눈이 맛이 갔었네요,..감사합니다!

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

문제

문제

출처

ICPC

LCA 문제 4%에서 틀린 점 좀 찾아주실 수 있나요..?

his130 6년 전 0

ntopia 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말