글 읽기 - 반례를 못찾겠어요 ㅠㅠ

jaewook5454 5년 전 0

어느 부분이 잘못된건지 확인해주실수 있나요?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>




using namespace std;

int depth[100001];

int anc[18][100001];

vector <int> grp[100001];
void dfs(int curr) {

	for (int j = 0; j < grp[curr].size(); j++) {
		int next = grp[curr][j];
		if (-1 == depth[next]) {

			anc[0][next] = curr;
			depth[next] = depth[curr] + 1;
			dfs(next);
		}

	}
}


int lca(int a, int b) {
	if (depth[a] < depth[b]) {

		for (int k = 17; k >= 0; k--) {

			while (a != b && depth[anc[k][b]] >= depth[a]) b = anc[k][b];

		}
	}
	else if (depth[a] > depth[b]) {

		for (int k = 17; k >= 0; k--) {

			while (a != b && depth[anc[k][a]] >= depth[a]) a = anc[k][a];
		}
	}
	
	
		for (int k = 17; k >= 0; k--)
		{
			if( anc[k][a] != anc[k][b])
			{
				while (a != b && anc[k][a] != anc[k][b]) {
					a = anc[k][a];
					b = anc[k][b];
				}
				
			}
		}
		int ans;
		if (a == b) ans =a;

		else ans = anc[0][a];
		
		printf("%d\n", ans);
		return 0;
}
int main() {
	//-1로 초기화
	int M;




	scanf("%d", &M);


	for (int i = 1; i <= M; i++) {
		depth[i] = -1;
		for (int k = 0; k < 18; k++) anc[k][i] = 0;
	}

	for (int i = 0; i < M-1 ; i++) {
		int a, b;
		//cout << "입력끝\n";

		scanf("%d", &a);
		scanf("%d", &b);
		//cout << "입력끝\n";

		grp[a].push_back(b);
		grp[b].push_back(a);

	}
	//cout << "123입력끝\n";
	depth[1] = 0;
	anc[0][1] = 1;

	dfs(1);
	for (int k = 1; k<18; k++)
	{
		for (int n = 1; n <= M; n++)
		{

			anc[k][n] = anc[k - 1][anc[k - 1][n]];

		}
	}

	int p;
	scanf("%d\n", &p);



	for (int i = 0; i < p; i++) {
		int a, b;
		scanf("%d", &a);

		scanf("%d", &b);
		lca(a, b);
	}


}

luniro 5년 전 2

출력:
1
21

정답:
21
21

jaewook5454 5년 전 0

해결했어요 감사합니다.

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

문제

문제

출처

ICPC

반례를 못찾겠어요 ㅠㅠ

jaewook5454 5년 전 0

luniro 5년 전 2

jaewook5454 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말