結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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);}}