結果

問題 No.2325 Skill Tree
ユーザー InTheBloom
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]);
        }
    }
}
0