結果

問題 No.277 根掘り葉掘り
ユーザー kou6839kou6839
提出日時 2015-09-06 18:03:27
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,776 bytes
コンパイル時間 2,631 ms
コンパイル使用メモリ 77,840 KB
実行使用メモリ 88,432 KB
最終ジャッジ日時 2023-09-26 09:42:26
合計ジャッジ時間 23,521 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] ne = new int[N];
		int[] ha = new int[N];
		for(int i=0;i<N;i++){
			ne[i]=10000000;
			ha[i]=10000000;
		}
		ArrayList<ArrayList<Integer>> g = new ArrayList<>();
		for(int i=0;i<N;i++) g.add(new ArrayList<>());
		
		for(int i=1;i<N;i++){
			int x = Integer.parseInt(sc.next())-1;
			int y = Integer.parseInt(sc.next())-1;
			g.get(x).add(y);
			g.get(y).add(x);
		}
		ArrayList<Integer> ne_list = new ArrayList<>();
		for(int i=1;i<N;i++){
			if(g.get(i).size()==1) ne_list.add(i);
		}
		Queue<Integer> que_l = new LinkedList<>();
		Queue<Integer> que_num = new LinkedList<>();
		boolean[] check = new boolean[N];
		
		que_l.add(0);
		que_num.add(0);
		while(!que_l.isEmpty()){
			int now = que_l.poll();
			int num = que_num.poll();
			check[now]=true;
			ha[now]=Math.min(ha[now], num);
			for(int i=0;i<g.get(now).size();i++){
				if(!check[g.get(now).get(i)]){
					que_l.add(g.get(now).get(i));
					que_num.add(num+1);
					check[now]=true;
				}
			}
		}
		
		for(int j: ne_list){
			que_l = new LinkedList<>();
			que_num = new LinkedList<>();
			check = new boolean[N];
			que_l.add(j);
			que_num.add(0);
			while(!que_l.isEmpty()){
				int now = que_l.poll();
				int num = que_num.poll();
				check[now]=true;
				ne[now]=Math.min(ne[now], num);
				for(int i=0;i<g.get(now).size();i++){
					if(!check[g.get(now).get(i)] && num+1<ne[g.get(now).get(i)]){
						que_l.add(g.get(now).get(i));
						que_num.add(num+1);
						check[now]=true;
					}
				}
			}
		}
		StringBuilder a = new StringBuilder();
		for(int i=0;i<N;i++){
			a.append(Math.min(ha[i], ne[i])+"\n");
		}
		System.out.println(a);
	}	
}
0