글 읽기 - 틀렸습니다.

holoveco 2년 전 0

어떤 부분이 틀렸는지 모르겠습니다..

혹시 틀린 케이스를 알수 있을까요..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, Q;
	static int parent[][];
	static int depth[];
	static ArrayList<Integer> adjList[];
	static int LGN = 18;
	public static void main(String[] args) throws Exception, IOException {
		// TODO Auto-generated method stub

		N = Integer.parseInt(br.readLine());
		
		parent = new int [LGN+1][N+1];
		depth = new int [N+1];
		adjList = new ArrayList[N+1];
				
		for( int i=1; i<=N ;i++)
		{
			adjList[i] = new ArrayList<>();
		}
		
		for(int i=1;i<N; i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adjList[a].add(b);
			adjList[b].add(a);
		}
		
		bfs(1,0);
		aces_find();
		
		Q = Integer.parseInt(br.readLine());
		for(int i = 0; i<Q; i++ )
		{
		    StringTokenizer st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
		    
    		System.out.println(LCA(a,b));
		}
		
		//bw.close();
		
		
		
	}
	
	static void bfs(int start, int dep)
	{
		Queue<Integer> que = new LinkedList<>();
		
		que.add(start);
		depth[start] = dep;
		while(!que.isEmpty())
		{
			int x= que.poll();
			for(int next : adjList[x])
			{
				if (parent[0][next] !=0) continue;
				parent[0][next] = x;
				depth[next] = depth[x] + 1;
				que.add(next);
			}
		}
	}
	
	static void aces_find()
	{
		for(int K=1;K<LGN; K++)
		{
			for(int V = 1; V<=N;V++)
			{
				parent[K][V] = parent[K-1][parent[K-1][V]];
			}
		}
	}
	
	static int LCA(int x, int y)
	{
		if (depth[x] > depth[y])
		{
			int temp = x;
			x = y;
			y = temp;
		}
		
		for(int i =LGN; i>=0;i--)
		{
			if (depth[y] - depth[x] >= (1<<i))
			{
				y = parent[i][y];
			}
		}
		
		if (x == y) return x;
		
		for(int i = LGN; i>=0; i--)
		{
			if (parent[i][x] != parent[i][y])
			{
				x = parent[i][x];
				y = parent[i][y];
			}
		}
		
		return parent[0][x];
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
}

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

문제

문제

출처

ICPC

틀렸습니다.

holoveco 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말