結果
問題 | No.2325 Skill Tree |
ユーザー | InTheBloom |
提出日時 | 2023-05-28 15:29:43 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 600 ms / 3,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 3,873 ms |
コンパイル使用メモリ | 167,408 KB |
実行使用メモリ | 46,080 KB |
最終ジャッジ日時 | 2023-09-04 20:30:31 |
合計ジャッジ時間 | 26,377 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 1 ms
4,384 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 187 ms
12,252 KB |
testcase_08 | AC | 185 ms
14,368 KB |
testcase_09 | AC | 237 ms
13,044 KB |
testcase_10 | AC | 276 ms
25,384 KB |
testcase_11 | AC | 290 ms
14,112 KB |
testcase_12 | AC | 548 ms
26,964 KB |
testcase_13 | AC | 540 ms
26,916 KB |
testcase_14 | AC | 549 ms
29,220 KB |
testcase_15 | AC | 548 ms
26,996 KB |
testcase_16 | AC | 549 ms
27,052 KB |
testcase_17 | AC | 547 ms
26,904 KB |
testcase_18 | AC | 546 ms
26,968 KB |
testcase_19 | AC | 539 ms
26,960 KB |
testcase_20 | AC | 541 ms
26,936 KB |
testcase_21 | AC | 550 ms
26,952 KB |
testcase_22 | AC | 542 ms
28,784 KB |
testcase_23 | AC | 537 ms
27,224 KB |
testcase_24 | AC | 534 ms
26,940 KB |
testcase_25 | AC | 532 ms
26,964 KB |
testcase_26 | AC | 534 ms
26,960 KB |
testcase_27 | AC | 600 ms
44,700 KB |
testcase_28 | AC | 599 ms
45,944 KB |
testcase_29 | AC | 595 ms
46,012 KB |
testcase_30 | AC | 595 ms
46,080 KB |
testcase_31 | AC | 590 ms
45,732 KB |
testcase_32 | AC | 578 ms
44,676 KB |
testcase_33 | AC | 580 ms
44,656 KB |
testcase_34 | AC | 580 ms
45,964 KB |
testcase_35 | AC | 588 ms
45,776 KB |
testcase_36 | AC | 598 ms
45,988 KB |
testcase_37 | AC | 597 ms
44,704 KB |
ソースコード
import std; void main () { int N = readln.split[0].to!int; // 覚えるために必要な技->覚えられる技 へと有向辺を張る int[][] vertex = new int[][](N, 0); int[] L; L ~= 0; foreach (i; 1..N) { auto buf = readln.split.to!(int[]); L ~= buf[0]; buf[1] -= 1; vertex[buf[1]] ~= i; } int Q = readln.split[0].to!int; solve(N, L, vertex, Q); } void solve (int N, int[] L, int[][] vertex, int Q) { // 技i(0<=i<=N-1)を覚えるために必要なコスト -1は覚えられない(依存関係がループしている) int[] cost = new int[](N); cost[0] = 0, cost[1..$] = -1; // BFS巡回 DList!int Que; Que.insertBack(0); while (!Que.empty) { int begin = Que.front; Que.removeFront; foreach (x; vertex[begin]) { if (cost[x] == -1) { cost[x] = max(L[x], cost[begin]); Que.insertBack(x); } } } int[] merge; foreach (x; cost) { if (x != -1) { merge ~= x; } } merge.sort; foreach (_; 0..Q) { auto buf = readln.split.to!(int[]); int query = buf[0], z = buf[1]; if (query == 1) { int left = 0, right = cast(int)merge.length; while (right - left != 1) { int center = (left + right) / 2; if (z < merge[center]) { right = center; } else { left = center; } } writeln(right); } else { writeln(cost[z-1]); } } }