結果
問題 | No.2325 Skill Tree |
ユーザー | Sagnik Ghosh |
提出日時 | 2023-06-06 03:45:49 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,309 ms / 3,000 ms |
コード長 | 8,766 bytes |
コンパイル時間 | 4,065 ms |
コンパイル使用メモリ | 106,540 KB |
実行使用メモリ | 90,684 KB |
最終ジャッジ日時 | 2023-08-28 10:01:56 |
合計ジャッジ時間 | 39,445 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 120 ms
55,888 KB |
testcase_01 | AC | 118 ms
55,960 KB |
testcase_02 | AC | 118 ms
55,992 KB |
testcase_03 | AC | 119 ms
55,968 KB |
testcase_04 | AC | 118 ms
55,960 KB |
testcase_05 | AC | 118 ms
55,828 KB |
testcase_06 | AC | 118 ms
55,576 KB |
testcase_07 | AC | 505 ms
64,520 KB |
testcase_08 | AC | 497 ms
55,904 KB |
testcase_09 | AC | 500 ms
64,664 KB |
testcase_10 | AC | 568 ms
77,912 KB |
testcase_11 | AC | 538 ms
70,128 KB |
testcase_12 | AC | 878 ms
88,284 KB |
testcase_13 | AC | 916 ms
89,688 KB |
testcase_14 | AC | 880 ms
89,544 KB |
testcase_15 | AC | 933 ms
90,180 KB |
testcase_16 | AC | 896 ms
88,504 KB |
testcase_17 | AC | 803 ms
88,176 KB |
testcase_18 | AC | 772 ms
88,144 KB |
testcase_19 | AC | 819 ms
88,196 KB |
testcase_20 | AC | 778 ms
89,796 KB |
testcase_21 | AC | 801 ms
88,220 KB |
testcase_22 | AC | 810 ms
88,360 KB |
testcase_23 | AC | 807 ms
88,624 KB |
testcase_24 | AC | 801 ms
89,832 KB |
testcase_25 | AC | 803 ms
88,156 KB |
testcase_26 | AC | 791 ms
88,168 KB |
testcase_27 | AC | 1,189 ms
89,684 KB |
testcase_28 | AC | 1,108 ms
88,048 KB |
testcase_29 | AC | 1,187 ms
89,276 KB |
testcase_30 | AC | 1,278 ms
90,684 KB |
testcase_31 | AC | 1,172 ms
89,620 KB |
testcase_32 | AC | 1,115 ms
89,500 KB |
testcase_33 | AC | 1,183 ms
89,740 KB |
testcase_34 | AC | 1,123 ms
89,720 KB |
testcase_35 | AC | 1,309 ms
89,620 KB |
testcase_36 | AC | 1,277 ms
87,560 KB |
testcase_37 | AC | 1,157 ms
88,660 KB |
ソースコード
// JAI SHREE RAM /* ░██████╗░█████╗░░██████╗░███╗░░██╗██╗██╗░░██╗░██████╗░██╗░░██╗░█████╗░░██████╗██╗░░██╗░█████╗░██████╗░███████╗ ██╔════╝██╔══██╗██╔════╝░████╗░██║██║██║░██╔╝██╔════╝░██║░░██║██╔══██╗██╔════╝██║░░██║██╔══██╗██╔══██╗╚════██║ ╚█████╗░███████║██║░░██╗░██╔██╗██║██║█████═╝░██║░░██╗░███████║██║░░██║╚█████╗░███████║██║░░╚═╝██████╔╝░░░░██╔╝ ░╚═══██╗██╔══██║██║░░╚██╗██║╚████║██║██╔═██╗░██║░░╚██╗██╔══██║██║░░██║░╚═══██╗██╔══██║██║░░██╗██╔══██╗░░░██╔╝░ ██████╔╝██║░░██║╚██████╔╝██║░╚███║██║██║░╚██╗╚██████╔╝██║░░██║╚█████╔╝██████╔╝██║░░██║╚█████╔╝██║░░██║░░██╔╝░░ ╚═════╝░╚═╝░░╚═╝░╚═════╝░╚═╝░░╚══╝╚═╝╚═╝░░╚═╝░╚═════╝░╚═╝░░╚═╝░╚════╝░╚═════╝░╚═╝░░╚═╝░╚════╝░╚═╝░░╚═╝░░╚═╝░░░ */ import java.util.*; import java.util.Map.Entry; import java.util.stream.*; import java.lang.*; import java.math.BigInteger; import java.text.DecimalFormat; import java.io.*; public class Main { static Scanner sc = new Scanner(System.in); static FastScanner fs = new FastScanner(); static PrintWriter out = new PrintWriter(System.out); static final Random random = new Random(); static final int mod = 1_000_000_007; static final int MAXN = 1000001; static StringBuilder sb = new StringBuilder(); static final int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; static final int[] dx8 = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy8 = { -1, 0, 1, -1, 1, -1, 0, 1 }; static final int[] dx9 = { -1, -1, -1, 0, 0, 0, 1, 1, 1 }, dy9 = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; static final double eps = 1e-10; static long [] larr = new long[100001]; static int cnt = 0, tmpSum = 0; private static void sagnik() throws IOException { 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]); } } out.flush(); } public static void main(String[] args) throws IOException { int t = 1; while(t-->0) sagnik(); } // Make t = 1 baby // dont worry bout me, i'm not high private static int arrMax(int[] A) {return Arrays.stream(A).max().getAsInt();} private static int arrMin(int[] A) {return Arrays.stream(A).min().getAsInt();} private static int arrSum(int[] A) {return Arrays.stream(A).sum();} private static int countNumInArr(int[] A, int n) {return (int) Arrays.stream(A).filter(x -> x == n).count();} private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } private static void reverse(int[] A) {int s=0,e=A.length-1;while(s<e){swap(A,s,e);s++;e--;}} private static void reverse(int[] A, int s) {int e=A.length-1;while(s<e){swap(A,s,e);s++;e--;}} private static void reverse(int[] A, int s, int e) {while(s<e){swap(A,s,e);s++;e--;}} private static int countSetBits(int number){int count=0; while(number>0){++count; number &= number-1;} return count;} private static boolean isEven(int i) { return (i & 1) == 0; } private static boolean isVowel(char c) { return c=='a' || c=='A' || c=='e' || c=='E' || c=='i' || c=='I' || c=='o' || c=='O' || c=='u' || c=='U';} private static boolean isPrime(int x) {if(x==1) return false; for(int i=2; i*i<=x; i++){if(x%i==0) return false;} return true;} public static boolean[] genSieve(int n) {boolean[] A = new boolean[n+1]; for(int i=0;i<n;i++) A[i] = true; for(int p=2; p*p <=n; p++) if(A[p]) for(int i = p*2; i<=n; i+=p) A[i] = false; return A;} private static int gcd(int a, int b) {if (b == 0) return a; return gcd(b, a % b);} private static int lcm(int a, int b) {return (a*b)/gcd(a, b);} private static int[] listToArr(List<Integer> x) {return x.stream().mapToInt(i -> i).toArray();} private static int[] setArray(int n) {int A[]=new int[n]; for(int i=0;i<n;i++) A[i]=sc.nextInt(); return A;} private static long[] lsetArray(int n) {long A[]=new long[n]; for(int i=0;i<n;i++) A[i]=sc.nextLong(); return A;} private static void prtList(List<Integer> x) {for(int i : x) {System.out.print(i+" ");}} private static void prtArr(int[] A) {System.out.println(Arrays.toString(A));} private static void prtArrWithSpce(int[] A) {for(int i=0;i<A.length;i++)System.out.print(A[i]+" ");} private static void prtArrWithSpce(int[] A, int s) {for(int i=s;i<A.length;i++)System.out.print(A[i]+" ");} private static void prtArrWithSpce(int[] A, int s, int e) {for(int i=s;i<=e;i++)System.out.print(A[i]+" ");} private static void debug(Object... o) {if(o.length != 0) System.err.println(Arrays.deepToString(o)); else System.err.println();} // DecimalFormat df = new DecimalFormat("#.###"); // DecimalFormat df = new DecimalFormat(); df.setMaximumFractionDigits(12); // System.out.println(df.format(input_Decimal_Here)); // fastIO cos why not public static class FastScanner { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static StringTokenizer st = new StringTokenizer(""); private static String next() throws IOException {while(!st.hasMoreTokens()) try {st=new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();} return st.nextToken();} private static int[] setArray(int n) throws IOException {int[] a = new int[n]; for (int i=0; i<n; i++) a[i] = nextInt(); return a;} private static long[] lsetArray(int n) throws IOException {long a[] = new long[n]; for(int i=0; i<n; i++) a[i] = nextLong(); return a;} private static int nextInt() throws IOException {return Integer.parseInt(next());} private static Long nextLong() throws IOException {return Long.parseLong(next());} private static double nextDouble() throws IOException {return Double.parseDouble(next());} private static char nextChar() throws IOException {return next().toCharArray()[0];} private static String nextString() throws IOException {return next();} private static String nextLine() throws IOException {return br.readLine();} private static String nextToken() throws IOException {while (st == null || !st.hasMoreElements()) {try {st = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}} return st.nextToken();} private static BigInteger nextBigInteger() throws IOException {return new BigInteger(next());} } }