結果
問題 | No.2325 Skill Tree |
ユーザー | 👑 kakel-san |
提出日時 | 2023-10-11 00:01:05 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 860 ms / 3,000 ms |
コード長 | 2,544 bytes |
コンパイル時間 | 3,620 ms |
コンパイル使用メモリ | 62,036 KB |
実行使用メモリ | 68,408 KB |
最終ジャッジ日時 | 2023-10-11 00:01:46 |
合計ジャッジ時間 | 32,051 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
15,628 KB |
testcase_01 | AC | 72 ms
15,688 KB |
testcase_02 | AC | 72 ms
15,744 KB |
testcase_03 | AC | 73 ms
15,624 KB |
testcase_04 | AC | 74 ms
15,768 KB |
testcase_05 | AC | 74 ms
17,740 KB |
testcase_06 | AC | 73 ms
19,680 KB |
testcase_07 | AC | 289 ms
31,652 KB |
testcase_08 | AC | 273 ms
33,844 KB |
testcase_09 | AC | 323 ms
36,196 KB |
testcase_10 | AC | 397 ms
42,236 KB |
testcase_11 | AC | 378 ms
39,976 KB |
testcase_12 | AC | 669 ms
58,204 KB |
testcase_13 | AC | 663 ms
58,160 KB |
testcase_14 | AC | 676 ms
58,304 KB |
testcase_15 | AC | 642 ms
58,420 KB |
testcase_16 | AC | 663 ms
58,216 KB |
testcase_17 | AC | 631 ms
58,216 KB |
testcase_18 | AC | 673 ms
58,372 KB |
testcase_19 | AC | 656 ms
58,244 KB |
testcase_20 | AC | 650 ms
58,248 KB |
testcase_21 | AC | 659 ms
58,224 KB |
testcase_22 | AC | 646 ms
58,160 KB |
testcase_23 | AC | 667 ms
58,396 KB |
testcase_24 | AC | 637 ms
58,312 KB |
testcase_25 | AC | 661 ms
58,204 KB |
testcase_26 | AC | 626 ms
58,236 KB |
testcase_27 | AC | 726 ms
64,536 KB |
testcase_28 | AC | 860 ms
64,520 KB |
testcase_29 | AC | 841 ms
68,408 KB |
testcase_30 | AC | 731 ms
64,656 KB |
testcase_31 | AC | 742 ms
64,568 KB |
testcase_32 | AC | 685 ms
65,616 KB |
testcase_33 | AC | 696 ms
66,620 KB |
testcase_34 | AC | 723 ms
66,584 KB |
testcase_35 | AC | 721 ms
61,140 KB |
testcase_36 | AC | 732 ms
61,204 KB |
testcase_37 | AC | 755 ms
62,232 KB |
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var n = NN; var map = NArr(n - 1); var q = NN; var query = NArr(q); var levels = Enumerable.Repeat(int.MaxValue, n).ToArray(); levels[0] = 0; var tree = new List<(int to, int lv)>[n]; for (var i = 0; i < n; ++i) tree[i] = new List<(int to, int lv)>(); for (var i = 0; i < map.Length; ++i) { tree[map[i][1] - 1].Add((i + 1, map[i][0])); } DFS(0, tree, levels); var dic = new Dictionary<int, int>(); for (var i = 0; i < levels.Length; ++i) { if (dic.ContainsKey(levels[i])) ++dic[levels[i]]; else dic[levels[i]] = 1; } dic[int.MaxValue] = 0; var llist = new List<int>(dic.Keys); llist.Sort(); var clist = new int[llist.Count]; for (var i = 0; i < llist.Count; ++i) { clist[i] = dic[llist[i]] + (i > 0 ? clist[i - 1] : 0); } var ans = new int[q]; for (var i = 0; i < q; ++i) { if (query[i][0] == 1) { var pos = LowerBound(0, query[i][1], llist); if (query[i][1] < llist[pos]) --pos; ans[i] = clist[pos]; } else { ans[i] = levels[query[i][1] - 1]; } } WriteLine(string.Join("\n", ans.Select(ai => ai == int.MaxValue ? -1 : ai))); } static void DFS(int cur, List<(int to, int lv)>[] tree, int[] levels) { foreach (var next in tree[cur]) { levels[next.to] = Math.Max(levels[cur], next.lv); DFS(next.to, tree, levels); } } static int LowerBound(int left, int min, List<int> list) { if (list[left] >= min) return left; var ng = left; var ok = list.Count; while (ok - ng > 1) { var center = (ng + ok) / 2; if (list[center] < min) ng = center; else ok = center; } return ok; } }