結果
問題 | No.2325 Skill Tree |
ユーザー | CuriousFairy315 |
提出日時 | 2023-05-28 13:58:37 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 910 ms / 3,000 ms |
コード長 | 10,064 bytes |
コンパイル時間 | 3,697 ms |
コンパイル使用メモリ | 91,968 KB |
実行使用メモリ | 86,268 KB |
最終ジャッジ日時 | 2023-08-27 08:46:33 |
合計ジャッジ時間 | 27,649 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 51 ms
50,100 KB |
testcase_01 | AC | 52 ms
50,288 KB |
testcase_02 | AC | 54 ms
50,188 KB |
testcase_03 | AC | 52 ms
50,272 KB |
testcase_04 | AC | 53 ms
50,128 KB |
testcase_05 | AC | 52 ms
50,140 KB |
testcase_06 | AC | 53 ms
50,224 KB |
testcase_07 | AC | 250 ms
57,852 KB |
testcase_08 | AC | 264 ms
65,312 KB |
testcase_09 | AC | 314 ms
67,872 KB |
testcase_10 | AC | 366 ms
69,856 KB |
testcase_11 | AC | 338 ms
65,664 KB |
testcase_12 | AC | 506 ms
81,312 KB |
testcase_13 | AC | 574 ms
81,172 KB |
testcase_14 | AC | 581 ms
81,220 KB |
testcase_15 | AC | 555 ms
81,228 KB |
testcase_16 | AC | 496 ms
80,868 KB |
testcase_17 | AC | 530 ms
79,260 KB |
testcase_18 | AC | 521 ms
79,412 KB |
testcase_19 | AC | 531 ms
79,236 KB |
testcase_20 | AC | 588 ms
79,668 KB |
testcase_21 | AC | 514 ms
79,324 KB |
testcase_22 | AC | 483 ms
81,324 KB |
testcase_23 | AC | 503 ms
80,044 KB |
testcase_24 | AC | 498 ms
81,736 KB |
testcase_25 | AC | 474 ms
81,752 KB |
testcase_26 | AC | 483 ms
81,716 KB |
testcase_27 | AC | 869 ms
82,548 KB |
testcase_28 | AC | 825 ms
84,032 KB |
testcase_29 | AC | 907 ms
83,588 KB |
testcase_30 | AC | 870 ms
84,164 KB |
testcase_31 | AC | 878 ms
86,268 KB |
testcase_32 | AC | 809 ms
80,876 KB |
testcase_33 | AC | 794 ms
85,360 KB |
testcase_34 | AC | 837 ms
83,236 KB |
testcase_35 | AC | 910 ms
82,164 KB |
testcase_36 | AC | 866 ms
81,916 KB |
testcase_37 | AC | 832 ms
83,272 KB |
ソースコード
import java.util.ArrayList; import java.util.PriorityQueue; import java.util.TreeMap; public class Main { public static void main(String[] args) { new Main(); } public Main() { FastScanner fs = new FastScanner(); java.io.PrintWriter out = new java.io.PrintWriter(System.out); solve(fs, out); out.flush(); } public void solve(FastScanner fs, java.io.PrintWriter out) { int N = fs.nextInt(); ArrayList<ArrayList<Integer>> graph = new ArrayList<>(N); for (int i = 0;i < N;++ i) graph.add(new ArrayList<>()); int[] L = new int[N]; L[0] = 1; final int INF = 1 << 30; for (int i = 1;i < N;++ i) { int l = fs.nextInt(), A = fs.nextInt() - 1; graph.get(A).add(i); L[i] = l + INF; } int Q = fs.nextInt(); class Pair { int vertex; int level; Pair(int v) { vertex = v; level = L[v]; } } PriorityQueue<Pair> pq = new PriorityQueue<>((l, r) -> Integer.compare(l.level, r.level)); pq.add(new Pair(0)); TreeMap<Integer, Integer> ans = new TreeMap<>(); ans.put(0, 0); while(!pq.isEmpty()) { Pair p = pq.poll(); if (L[p.vertex] < p.level) continue; int now = p.vertex; if (ans.get(p.level) == null) ans.put(p.level, ans.lastEntry().getValue()); ans.merge(p.level, 1, (l, r) -> l + r); for (int next : graph.get(now)) { if (L[next] <= L[now]) continue; L[next] = L[next] >= INF ? Math.max(L[next] - INF, L[now]) : L[now]; pq.add(new Pair(next)); } } while(Q --> 0) { if (fs.nextInt() == 1) { int x = fs.nextInt(); out.println(ans.floorEntry(x).getValue()); } else { int y = fs.nextInt() - 1; out.println(L[y] >= INF ? -1 : L[y]); } } } final int MOD = 998_244_353; int plus(int n, int m) { int sum = n + m; if (sum >= MOD) sum -= MOD; return sum; } int minus(int n, int m) { int sum = n - m; if (sum < 0) sum += MOD; return sum; } int times(int n, int m) { return (int)((long)n * m % MOD); } int divide(int n, int m) { return times(n, IntMath.pow(m, MOD - 2, MOD)); } int[] fact, invf; void calc(int len) { len += 2; fact = new int[len]; invf = new int[len]; fact[0] = fact[1] = invf[0] = invf[1] = 1; for (int i = 2;i < fact.length;++ i) fact[i] = times(fact[i - 1], i); invf[len - 1] = divide(1, fact[len - 1]); for (int i = len - 1;i > 1;-- i) invf[i - 1] = times(i, invf[i]); } int comb(int n, int m) { if (n < m) return 0; return times(fact[n], times(invf[n - m], invf[m])); } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] buffer = new byte[8192]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (java.io.IOException e) { e.printStackTrace(); } return buflen > 0; } private byte readByte() { return hasNextByte() ? buffer[ptr++ ] : -1; } private static boolean isPrintableChar(byte c) { return 32 < c || c < 0; } private static boolean isNumber(int c) { return '0' <= c && c <= '9'; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++ ; return hasNextByte(); } public String next() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); byte b; while (isPrintableChar(b = readByte())) sb.appendCodePoint(b); return sb.toString(); } public final char nextChar() { if (!hasNext()) throw new java.util.NoSuchElementException(); return (char)readByte(); } public final long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public final int nextInt() { if (!hasNext()) throw new java.util.NoSuchElementException(); int n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public double nextDouble() { return Double.parseDouble(next()); } } class Arrays { public static void sort(final int[] array) { sort(array, 0, array.length); } public static void sort(final int[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new int[array.length]); } private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) { if (to - from <= 512) { java.util.Arrays.sort(a, from, to); return; } final int BUCKET_SIZE = 256; final int INT_RECURSION = 4; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(a[i] >>> shift & MASK) + 1]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = a[i] >>> shift & MASK; bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < INT_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void sort(final long[] array) { sort(array, 0, array.length); } public static void sort(final long[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new long[array.length]); } private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) { final int BUCKET_SIZE = 256; final int LONG_RECURSION = 8; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(int) ((a[i] >>> shift & MASK) + 1)]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = (int) (a[i] >>> shift & MASK); bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < LONG_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void reverse(int[] array) { reverse(array, 0, array.length); } public static void reverse(int[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { int swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void reverse(long[] array) { reverse(array, 0, array.length); } public static void reverse(long[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { long swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void shuffle(int[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; int swap = array[i]; array[i] = array[j]; array[j] = swap; } } public static void shuffle(long[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; long swap = array[i]; array[i] = array[j]; array[j] = swap; } } } class IntMath { public static int gcd(int a, int b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static int gcd(int... array) { int ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long gcd(long a, long b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static long gcd(long... array) { long ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long lcm(long a, long b) { return a / gcd(a, b) * b; } public static int pow(int a, int b) { int ans = 1; for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static long pow(long a, long b) { long ans = 1; for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static int pow(int a, long b, int mod) { if (b < 0) b = b % (mod - 1) + mod - 1; long ans = 1; for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod; return (int)ans; } public static int pow(long a, long b, int mod) { return pow((int)(a % mod), b, mod); } public static int floorsqrt(long n) { return (int)Math.sqrt(n + 0.1); } public static int ceilsqrt(long n) { return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1; } }