結果

問題 No.277 根掘り葉掘り
コンテスト
ユーザー kou6839
提出日時 2015-09-06 18:01:35
言語 Java
(openjdk 23)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,963 bytes
コンパイル時間 2,521 ms
コンパイル使用メモリ 84,596 KB
実行使用メモリ 84,460 KB
最終ジャッジ日時 2024-07-19 04:38:18
合計ジャッジ時間 22,041 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.ObjectInputStream.GetField;
import java.lang.reflect.Array;
import java.net.NetworkInterface;
import java.util.*;
import java.util.zip.Inflater;

import javax.swing.plaf.synth.SynthSpinnerUI;


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