글 읽기 - 10%에서 틀렸다고 하는데 도무지 이유를 모르겠네요

yoodly 5년 전 0

안녕하세요

LCA는 4%에서, LCA 2는 10%에서 틀렸다고 하는데 이유를 모르겠습니다.

혹시 적절한 반례가 있을까요? 쭉 일렬로 연결된 케이스나 노드 2개짜리도 테스트해 보았는데 답이 잘 나오더라구요.

조언 부탁드립니다 ㅠ

import java.util.*;
import java.io.*;

public class Main {
	static int size;
	static ArrayList<Integer>[] tree;
	static int[] level;
	static int[][] par;
	static BufferedWriter bw;
	public static void main(String[] args) throws Exception {
		int N, M, a, b;
		StringTokenizer st;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine().trim());		
		tree = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) tree[i] = new ArrayList<Integer>();
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			tree[a].add(b);
			tree[b].add(a);
		}
		
		// 노드의 깊이 배열과 조상 배열을 구성
		size = 1; while ((int)Math.pow(2, size) < N) size++;  // 노드의 깊이 크기
		par = new int[N+1][size+1]; 
		level = new int[N+1]; Arrays.fill(level, -1); 
		dfs(1, 1);
		for (int i = 1; i <= N; i++) {  // 각 정점들의 2^i 번째 조상을 채우자
			for (int j = 1; j <= size; j++)
				par[i][j] = par[par[i][j-1]][j-1];
		}
		
		// 노드 쌍에 대한 공통 조상 구하기
		M = Integer.parseInt(br.readLine().trim());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			bw.append(lca(a, b)+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void dfs(int from, int depth) {
		int to;
		level[from] = depth;
		ArrayList<Integer> ar = tree[from];
		for (int i = 0; i < ar.size(); i++) {
			to = ar.get(i);
			if (level[to] != -1) continue;
			par[to][0] = from;
			dfs(to, depth+1);
		}
	}
	
	static int lca(int a, int b) {
		if (level[a] > level[b]) {
			int tmp = b; b = a; a = tmp;
		}
		for (int i = size; i >= 0; i--) {
			if (level[par[b][i]] >= level[a])
				b = par[b][i];
		}
		if (a == b) return a;
		for (int i = size; i >= 0; i--) {
			if (par[a][i] != par[b][i]) {
				a = par[a][i];
				b = par[b][i];
			}
		}
		return (par[a][0]);
	}
}

djm03178 5년 전 1

https://www.acmicpc.net/board/... 에 도움이 될만한 답변이 있습니다.

yoodly 5년 전 0

정말로 감사드립니다!!

사실 다른 분들이 지적하신 부분을 저랑 다르게(?) 코딩 하신 것은 보았고, 1번 노드가 2^i번째 조상에서자꾸 누락되는 점이 이상하긴 했는데, 이걸 같이 생각하지 못했네요.

도움 감사드립니다~~

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

문제

문제

출처

ICPC

10%에서 틀렸다고 하는데 도무지 이유를 모르겠네요

yoodly 5년 전 0

djm03178 5년 전 1

yoodly 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말