結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2015-09-05 09:09:22 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 669 ms / 3,000 ms |
コード長 | 2,602 bytes |
コンパイル時間 | 3,693 ms |
コンパイル使用メモリ | 78,908 KB |
実行使用メモリ | 64,340 KB |
最終ジャッジ日時 | 2024-07-19 03:45:53 |
合計ジャッジ時間 | 11,478 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintStream;import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Iterator;import java.util.List;import java.util.Queue;public class Main_yukicoder277 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);int n = sc.nextInt();List<ArrayList<Integer>> edges = new ArrayList<ArrayList<Integer>>();for (int i = 0; i < n; i++) {edges.add(new ArrayList<Integer>());}for (int i = 0; i < n - 1; i++) {int x = sc.nextInt() - 1;int y = sc.nextInt() - 1;edges.get(x).add(y);edges.get(y).add(x);}Queue<Integer> q = new ArrayDeque<Integer>();int[] d = new int[n];final int INF = Integer.MAX_VALUE;Arrays.fill(d, INF);q.add(0);d[0] = 0;for (int i = 0; i < n; i++) {if (edges.get(i).size() == 1) {q.add(i);d[i] = 0;}}while (!q.isEmpty()) {int u = q.remove();for (int e : edges.get(u)) {if (d[e] > d[u] + 1) {q.add(e);d[e] = d[u] + 1;}}}for (int e : d) {pr.println(e);}pr.close();sc.close();}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}