글 읽기 - 테스트케이스를 좀 더 주실수 있나요?

ysjloveksj 7년 전 0

문제에 주어진 input에 대한 결과는 맞는데

틀렸다고 해서요...

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
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 {
	
	private static int N, M;
	private static StringTokenizer st;
	private static int par[][];
	private static ArrayList<Integer> con[];
	private static int dep[];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader br = new BufferedReader(new FileReader("C:\\Users\\Administrator\\workspace\\input\\LCA_11437.txt"));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		//초기화
		par = new int[N+1][16];//2 ≤ N ≤ 50000 / 2^16 > 50000
		con = new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			con[i] = new ArrayList<>();
		}
		dep = new int[N+1];
		
		for(int i=1;i<=N-1;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int parent, child;
			if(a < b) {
				parent = a;
				child = b;
			} else {
				parent = b;
				child = a;
			}
			par[child][0] = parent;
			con[parent].add(child);
		}
		
		//Sparse Table
		for(int k=1;k<16;k++) {
			for(int i=1;i<=N;i++) {
				par[i][k] = par[par[i][k-1]][k-1];
			}
		}
		
		//Depth
		Queue<Integer> que = new LinkedList<>();
		que.add(1);
		while(!que.isEmpty()) {
			int q = que.poll();
			for(int t : con[q]) {
				dep[t] = dep[q]+1;
				que.add(t);
			}
		}
		
		M = Integer.parseInt(br.readLine());
		for(int i=1;i<=M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			bw.write(lca(a,b)+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static int lca(int a, int b) {

		//1.swap
		if(dep[a] < dep[b]) {
			a^=b;
			b^=a;
			a^=b;
		}
		//2.1<<i & dep[a]-dep[b]
		for(int i=0;i<16;i++) {
			if(((1<<i)&(dep[a]-dep[b])) != 0) {
				a = par[a][i];
			}
		}
		//3.if(a==b) return a;
		if(a == b) 
			return a;
		//4.for(int i=16;i-->0;) if(par[a][i] != par[b][i]) -> a=par[a][i]; b=par[b][i];
		for(int i=16;i-->0;) {
			if(par[a][i] != par[b][i]) {
				a=par[a][i]; 
				b=par[b][i];
			}
		}
		
		return par[a][0];
	}
}

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

문제

문제

출처

ICPC

테스트케이스를 좀 더 주실수 있나요?

ysjloveksj 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말