結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2017-10-06 00:33:31 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 315 ms / 3,000 ms |
コード長 | 3,449 bytes |
コンパイル時間 | 1,086 ms |
コンパイル使用メモリ | 109,056 KB |
実行使用メモリ | 46,976 KB |
最終ジャッジ日時 | 2024-11-16 21:33:42 |
合計ジャッジ時間 | 6,232 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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.Text;using System.Threading.Tasks;namespace ProgrammingContest{class MainClass{Scanner sc;static void Main(string[] args){new MainClass().Solve();}struct Point{public double x, y;}const bool DEBUG = false; // TODO: must check!!void Solve(){if (DEBUG){string backPath = "..";char dirSep = System.IO.Path.DirectorySeparatorChar;string inFilePath = backPath + dirSep + backPath + dirSep + "in.txt";sc = new Scanner(new System.IO.StreamReader(inFilePath));}else{sc = new Scanner();}int N = sc.NextInt;G = new List<int>[N].Select(lst => new List<int>()).ToArray();ans = new int[N].Select(el => INF).ToArray();for (int i = 0; i < N - 1; i++){int a = sc.NextInt - 1;int b = sc.NextInt - 1;G[a].Add(b);G[b].Add(a);}dfs(0, -1, 0);for (int i = 1; i < N; i++){if (G[i].Count <= 1){dfs(i, -1, 0);}}Console.WriteLine(String.Join("\n", Array.ConvertAll(ans, el => el.ToString())));}void dfs(int now, int prev, int cost){ans[now] = Math.Min(ans[now], cost);foreach (int el in G[now]){if (el != prev){if (cost + 1 < ans[el]){dfs(el, now, cost + 1);}}}}List<int>[] G;const int INF = (int)1e9;int[] ans;}class Scanner{Queue<String> buffer;char[] sep;System.IO.TextReader reader;public Scanner(System.IO.TextReader reader = null){this.buffer = new Queue<string>();this.sep = new char[] { ' ' };this.reader = (reader ?? Console.In);}private void CheckBuffer(){if (this.buffer.Count == 0){String[] sreArray = this.reader.ReadLine().Split(this.sep);foreach (String elStr in sreArray){this.buffer.Enqueue(elStr);}}}public String Next{get{this.CheckBuffer();return this.buffer.Dequeue();}}public int NextInt{get{return int.Parse(this.Next);}}public double NextDouble{get{return double.Parse(this.Next);}}public long NextLong{get{return long.Parse(this.Next);}}public bool IsEmpty{get{this.CheckBuffer();return this.buffer.Count == 0;}}}}