結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 13:58:37 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,020 ms / 3,000 ms |
コード長 | 10,064 bytes |
コンパイル時間 | 5,484 ms |
コンパイル使用メモリ | 91,964 KB |
実行使用メモリ | 72,632 KB |
最終ジャッジ日時 | 2024-12-26 22:37:24 |
合計ジャッジ時間 | 32,035 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
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();don = 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();don = 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;}}