結果

問題 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]);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0