結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:25:38 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 243 ms / 3,000 ms |
コード長 | 2,347 bytes |
コンパイル時間 | 995 ms |
コンパイル使用メモリ | 31,488 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-12-27 01:07:55 |
合計ジャッジ時間 | 9,567 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include<stdio.h>int h[200005], hl;int l[200005], a[200005];int comp_h(int x, int y,int z){if (z == 0){if (a[h[x]] > a[h[y]])return 1;elsereturn -1;}else{if (h[x] > h[y])return 1;elsereturn -1;}}void swap_h(int x, int y){int f = h[x];h[x] = h[y];h[y] = f;return;}void push(int ne, int z){h[hl] = ne;int p = hl;hl++;for (; p > 0; p = (p - 1) / 2)if (comp_h((p - 1) / 2, p, z) > 0)swap_h((p - 1) / 2, p);return;}int pop(int z){hl--;swap_h(0, hl);int p = 0;for (;;){if (2 * p + 2 < hl){if (comp_h(2 * p + 1, 2 * p + 2, z) > 0){if (comp_h(p, 2 * p + 2, z) > 0)swap_h(p, 2 * p + 2);p = 2 * p + 2;}else{if (comp_h(p, 2 * p + 1, z) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}}else if (2 * p + 1 < hl){if (comp_h(p, 2 * p + 1, z) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}elsebreak;}return h[hl];}int c[200005];int maxlevel[200005];int stack[200005], ss;int sorted_maxlevel[200005];int main(){int n;scanf("%d", &n);int i;for (i = 1; i < n; i++){scanf("%d %d", &l[i], &a[i]);a[i]--;}l[0] = a[0] = 0;hl = 0;for (i = 0; i < n; i++)push(i, 0);for (i = 0; i < n; i++)c[i] = pop(0);c[n] = n;a[n] = -1;for (i = 0; i < n; i++)maxlevel[i] = -1;maxlevel[0] = 0;stack[0] = 0;ss = 1;int min, mid, max;while (ss > 0){ss--;i = stack[ss];min = -1;max = n;while (max - min > 1){mid = (max + min) / 2;if (a[c[mid]] < i)min = mid;elsemax = mid;}for (; a[c[max]] == i; max++){if (maxlevel[c[max]] >= 0)continue;maxlevel[c[max]] = maxlevel[i];if (maxlevel[i] < l[c[max]])maxlevel[c[max]] = l[c[max]];stack[ss] = c[max];ss++;}}for (i = 0; i < n; i++)push(maxlevel[i], 1);ss = 0;for (i = 0; i < n; i++){sorted_maxlevel[ss] = pop(1);if (sorted_maxlevel[ss] >= 0)ss++;}int q;scanf("%d", &q);int t, x;for (; q > 0; q--){scanf("%d %d", &t, &x);if (t == 1){min = -1;max = ss;while (max - min > 1){mid = (max + min) / 2;if (sorted_maxlevel[mid] > x)max = mid;elsemin = mid;}printf("%d\n", max);}else{printf("%d\n", maxlevel[x - 1]);}}return 0;}