結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:29:43 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 532 ms / 3,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 1,848 ms |
コンパイル使用メモリ | 181,464 KB |
実行使用メモリ | 45,672 KB |
最終ジャッジ日時 | 2024-06-22 18:03:26 |
合計ジャッジ時間 | 21,870 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
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]);}}}