結果
問題 | No.912 赤黒木 |
ユーザー | ei1333333 |
提出日時 | 2019-10-18 12:59:14 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 824 ms / 3,000 ms |
コード長 | 2,066 bytes |
コンパイル時間 | 1,565 ms |
コンパイル使用メモリ | 63,888 KB |
実行使用メモリ | 94,388 KB |
最終ジャッジ日時 | 2023-09-07 20:36:23 |
合計ジャッジ時間 | 18,351 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
20,744 KB |
testcase_01 | AC | 57 ms
18,668 KB |
testcase_02 | AC | 61 ms
20,728 KB |
testcase_03 | AC | 61 ms
22,776 KB |
testcase_04 | AC | 61 ms
20,888 KB |
testcase_05 | AC | 61 ms
20,800 KB |
testcase_06 | AC | 61 ms
20,756 KB |
testcase_07 | AC | 61 ms
22,872 KB |
testcase_08 | AC | 58 ms
20,840 KB |
testcase_09 | AC | 61 ms
22,936 KB |
testcase_10 | AC | 58 ms
18,848 KB |
testcase_11 | AC | 60 ms
22,832 KB |
testcase_12 | AC | 663 ms
47,348 KB |
testcase_13 | AC | 689 ms
49,920 KB |
testcase_14 | AC | 654 ms
48,548 KB |
testcase_15 | AC | 699 ms
50,000 KB |
testcase_16 | AC | 676 ms
49,116 KB |
testcase_17 | AC | 683 ms
49,292 KB |
testcase_18 | AC | 652 ms
46,516 KB |
testcase_19 | AC | 635 ms
46,044 KB |
testcase_20 | AC | 628 ms
45,956 KB |
testcase_21 | AC | 617 ms
45,772 KB |
testcase_22 | AC | 625 ms
50,988 KB |
testcase_23 | AC | 629 ms
47,080 KB |
testcase_24 | AC | 642 ms
51,028 KB |
testcase_25 | AC | 681 ms
47,220 KB |
testcase_26 | AC | 690 ms
47,872 KB |
testcase_27 | AC | 660 ms
48,960 KB |
testcase_28 | AC | 824 ms
92,352 KB |
testcase_29 | AC | 812 ms
94,020 KB |
testcase_30 | AC | 818 ms
94,388 KB |
testcase_31 | AC | 760 ms
87,428 KB |
ソースコード
using System; using System.Collections.Generic; class Program { Scanner cin; int N; List<int>[] g; int[] sub; int[,] dp; void rec(int idx, int par) { int[] dp2 = { 0, 0, 0 }; foreach(var to in g[idx]) { if (to == par) continue; rec(to, idx); sub[idx] += sub[to]; int[] dp3 = { 10101010, 10101010, 10101010 }; for (int i = 0; i < 3; i++) { for(int j = 0; i + j < 3; j++) { dp3[i + j] = Math.Min(dp3[i + j], dp2[i] + dp[to, j] + (sub[to] + j) % 2); } } for (int i = 0; i < 3; i++) { dp2[i] = dp3[i]; } } for(int i = 0; i < 3; i++) { dp[idx, i] = dp2[i]; } } void myon() { cin = new Scanner(); N = cin.nextInt(); g = new List<int>[N]; for(int i = 0; i < N; i++) { g[i] = new List<int>(); } for(int i = 1; i < N; i++) { int a = cin.nextInt() - 1; int b = cin.nextInt() - 1; g[a].Add(b); g[b].Add(a); } sub = new int[N]; for(int i = 1; i < N; i++) { int a = cin.nextInt() - 1; int b = cin.nextInt() - 1; sub[a] = 1 - sub[a]; sub[b] = 1 - sub[b]; } dp = new int[N, 3]; rec(0, -1); Console.WriteLine(dp[0, 2] + (N - 1)); } static void Main(string[] args) { new Program().myon(); } } class Scanner { string[] s; int i; readonly char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); if (s.Length == 0) return next(); i = 0; return s[i++]; } public string nextLine() { return Console.ReadLine(); } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }