結果

問題 No.277 根掘り葉掘り
ユーザー kou6839kou6839
提出日時 2015-09-06 17:53:27
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 1,841 bytes
コンパイル時間 2,562 ms
コンパイル使用メモリ 86,420 KB
実行使用メモリ 115,396 KB
最終ジャッジ日時 2023-09-26 09:36:46
合計ジャッジ時間 10,505 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
60,596 KB
testcase_01 AC 127 ms
55,976 KB
testcase_02 AC 127 ms
55,776 KB
testcase_03 AC 155 ms
55,992 KB
testcase_04 AC 161 ms
55,800 KB
testcase_05 AC 161 ms
55,448 KB
testcase_06 AC 161 ms
55,592 KB
testcase_07 AC 163 ms
55,556 KB
testcase_08 AC 129 ms
55,836 KB
testcase_09 AC 1,578 ms
82,500 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

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 = sc.nextInt()-1;
			int y = sc.nextInt()-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)]){
						que_l.add(g.get(now).get(i));
						que_num.add(num+1);
						check[now]=true;
					}
				}
			}
		}
		for(int i=0;i<N;i++){
			System.out.println(Math.min(ha[i], ne[i]));
		}
	}	
}
0