結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-04 22:49:15 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 285 ms / 3,000 ms |
コード長 | 3,910 bytes |
コンパイル時間 | 2,718 ms |
コンパイル使用メモリ | 108,800 KB |
実行使用メモリ | 36,596 KB |
最終ジャッジ日時 | 2024-07-19 01:28:47 |
合計ジャッジ時間 | 7,076 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;using System.IO;using System.Text;using System.Numerics;namespace Solver{class Program{const int M = 1000000007;const double eps = 1e-9;static void Main(){var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };var sc = new Scan();int n = sc.Int;var next = new List<int>[n];var par = new int[n];var leaf = new int[n];for (int i = 0; i < n; i++){next[i] = new List<int>();par[i] = M;leaf[i] = M;}for (int i = 0; i < n - 1; i++){var a = sc.IntArr;next[a[0] - 1].Add(a[1] - 1);next[a[1] - 1].Add(a[0] - 1);}par[0] = 0;var q = new Queue<int>();q.Enqueue(0);while (q.Count > 0){var p = q.Dequeue();foreach (var item in next[p]){if (par[item] > par[p] + 1){par[item] = par[p] + 1;q.Enqueue(item);}}}q = new Queue<int>();for (int i = 0; i < n; i++){if (next[i].Count == 1){leaf[i] = 0;q.Enqueue(i);}}while (q.Count > 0){var p = q.Dequeue();foreach (var item in next[p]){if (leaf[item] > leaf[p] + 1){leaf[item] = leaf[p] + 1;q.Enqueue(item);}}}for (int i = 0; i < n; i++)sw.WriteLine(Math.Min(par[i], leaf[i]));sw.Flush();}}class Scan{public int Int { get { return int.Parse(Console.ReadLine().Trim()); } }public long Long { get { return long.Parse(Console.ReadLine().Trim()); } }public string Str { get { return Console.ReadLine().Trim(); } }public int[] IntArr { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToArray(); } }public int[] IntArrWithSep(char sep) { return Console.ReadLine().Trim().Split(sep).Select(int.Parse).ToArray(); }public long[] LongArr { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToArray(); } }public double[] DoubleArr { get { return Console.ReadLine().Split().Select(double.Parse).ToArray(); } }public string[] StrArr { get { return Console.ReadLine().Trim().Split(); } }public List<int> IntList { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToList(); } }public List<long> LongList { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToList(); } }public void Multi(out int a, out int b) { var arr = IntArr; a = arr[0]; b = arr[1]; }public void Multi(out int a, out int b, out int c) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; }public void Multi(out int a, out int b, out int c, out int d) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; d = arr[3]; }public void Multi(out int a, out string b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1]; }public void Multi(out int a, out char b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1][0]; }public void Multi(out long a, out long b) { var arr = LongArr; a = arr[0]; b = arr[1]; }public void Multi(out string a, out string b) { var arr = StrArr; a = arr[0]; b = arr[1]; }}}