結果
問題 | No.1582 Vertexes vs Edges |
ユーザー |
|
提出日時 | 2021-07-02 22:40:36 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 197 ms / 2,000 ms |
コード長 | 1,245 bytes |
コンパイル時間 | 2,337 ms |
コンパイル使用メモリ | 116,572 KB |
実行使用メモリ | 36,600 KB |
最終ジャッジ日時 | 2024-06-29 12:32:42 |
合計ジャッジ時間 | 7,393 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
コンパイルメッセージ
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 static System.Console; using System.Linq; class yuki302 { static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat<int>(0, n).Select(_ => NList).ToArray(); static void Main() { var n = int.Parse(ReadLine()); var map = NMap(n - 1); var tree = new List<int>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>(); foreach (var edge in map) { tree[edge[0] - 1].Add(edge[1] - 1); tree[edge[1] - 1].Add(edge[0] - 1); } var list = Enumerable.Repeat(int.MaxValue, n).ToArray(); DFS(-1, 0, tree, list); WriteLine(list.Count(c => c % 2 == 1)); } static int DFS(int prev, int pos, List<int>[] tree, int[] list) { var val = int.MaxValue; if (tree[pos].Count == 1 && tree[pos][0] == prev) { val = 1; } else foreach (var next in tree[pos]) { if (next == prev) continue; val = Math.Min(val, DFS(pos, next, tree, list)); } val = (val + 1) % 2; list[pos] = val; return val; } }