結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2016-05-12 22:19:16 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,094 ms / 3,000 ms |
コード長 | 4,267 bytes |
コンパイル時間 | 1,268 ms |
コンパイル使用メモリ | 109,696 KB |
実行使用メモリ | 103,672 KB |
最終ジャッジ日時 | 2024-10-05 14:06:37 |
合計ジャッジ時間 | 11,636 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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.Text;using System.Linq;class Program{public void Proc(){Reader.IsDebug = false;int pointCount = int.Parse(Reader.ReadLine());Dictionary<int, List<int>> lineDic = new Dictionary<int, List<int>>();for(int i=0; i<pointCount - 1; i++) {int[] inpt = Reader.GetInt();if(!lineDic.ContainsKey(inpt[0])) {lineDic.Add(inpt[0], new List<int>());}lineDic[inpt[0]].Add(inpt[1]);if(!lineDic.ContainsKey(inpt[1])) {lineDic.Add(inpt[1], new List<int>());}lineDic[inpt[1]].Add(inpt[0]);}lineDic.ToList().ForEach(a=>this.TreeDic.Add(a.Key, new TreeNode(a.Key)));this.SetTree(1, lineDic);Queue<int> task = new Queue<int>();this.TreeDic.Where(a=>a.Value.Items.Count == 0).ToList().ForEach(b=>task.Enqueue(b.Key));while (task.Count > 0){int key = task.Dequeue();TreeNode target = TreeDic[key];if(target.Parent != null && (target.Parent.FarFromLeaf == 0 || target.Parent.FarFromLeaf > target.FarFromLeaf + 1)) {target.Parent.FarFromLeaf = target.FarFromLeaf + 1;task.Enqueue(target.Parent.ID);}target.Items.ForEach((a)=>{if((a.FarFromLeaf == 0 && a.Items.Count > 0) || a.FarFromLeaf > target.FarFromLeaf + 1) {a.FarFromLeaf = target.FarFromLeaf + 1;task.Enqueue(a.ID);}});}this.TreeDic.OrderBy(a=>a.Key).ToList().ForEach(b=>Console.WriteLine(Math.Min(b.Value.FarFromLeaf, b.Value.FarFromRoot)));}private void SetTree(int parent, Dictionary<int, List<int>>dic) {dic[parent].ForEach((a)=>{if(TreeDic[parent].Parent == null || a != TreeDic[parent].Parent.ID) {TreeDic[parent].Add(TreeDic[a]);}});TreeDic[parent].Items.ForEach(a=>this.SetTree(a.ID, dic));}Dictionary<int, TreeNode> TreeDic = new Dictionary<int, TreeNode>();public class TreeNode {public int ID;public TreeNode Parent;public List<TreeNode> Items = new List<TreeNode>();public int FarFromRoot;public int FarFromLeaf;public void Add(TreeNode child) {this.Items.Add(child);child.Parent = this;child.FarFromRoot = this.FarFromRoot + 1;child.RefreshFarFromRoot();}private void RefreshFarFromRoot() {if(this.Parent == null) {this.FarFromRoot = 0;} else{this.FarFromRoot = this.Parent.FarFromRoot + 1;}if(this.Items.Count > 0) {this.Items.ForEach(a=>a.RefreshFarFromRoot());}}public TreeNode(int id) {this.ID = id;}}public class Reader{public static bool IsDebug = true;private static String PlainInput = @"";private static System.IO.StringReader Sr = null;public static string ReadLine(){if (IsDebug){if (Sr == null){Sr = new System.IO.StringReader(PlainInput.Trim());}return Sr.ReadLine();}else{return Console.ReadLine();}}public static int[] GetInt(char delimiter = ' ', bool trim = false){string inptStr = ReadLine();if (trim){inptStr = inptStr.Trim();}string[] inpt = inptStr.Split(delimiter);int[] ret = new int[inpt.Length];for (int i = 0; i < inpt.Length; i++){ret[i] = int.Parse(inpt[i]);}return ret;}}static void Main(){Program prg = new Program();prg.Proc();}}