結果

問題 No.277 根掘り葉掘り
ユーザー kou6839kou6839
提出日時 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);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0