結果

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

ソースコード

diff #
プレゼンテーションモードにする

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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0