結果

問題 No.2325 Skill Tree
ユーザー Sagnik GhoshSagnik Ghosh
提出日時 2023-06-06 03:45:49
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,368 ms / 3,000 ms
コード長 8,766 bytes
コンパイル時間 3,148 ms
コンパイル使用メモリ 95,028 KB
実行使用メモリ 77,412 KB
最終ジャッジ日時 2024-06-09 05:35:53
合計ジャッジ時間 40,924 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 133 ms
42,160 KB
testcase_01 AC 134 ms
41,916 KB
testcase_02 AC 131 ms
42,244 KB
testcase_03 AC 130 ms
42,036 KB
testcase_04 AC 132 ms
42,280 KB
testcase_05 AC 132 ms
41,920 KB
testcase_06 AC 120 ms
41,224 KB
testcase_07 AC 517 ms
53,440 KB
testcase_08 AC 537 ms
57,344 KB
testcase_09 AC 569 ms
55,480 KB
testcase_10 AC 681 ms
66,500 KB
testcase_11 AC 630 ms
58,256 KB
testcase_12 AC 997 ms
75,452 KB
testcase_13 AC 993 ms
75,640 KB
testcase_14 AC 974 ms
75,740 KB
testcase_15 AC 986 ms
75,628 KB
testcase_16 AC 977 ms
75,588 KB
testcase_17 AC 966 ms
76,132 KB
testcase_18 AC 967 ms
75,900 KB
testcase_19 AC 952 ms
75,772 KB
testcase_20 AC 962 ms
76,256 KB
testcase_21 AC 976 ms
75,860 KB
testcase_22 AC 965 ms
76,156 KB
testcase_23 AC 948 ms
76,064 KB
testcase_24 AC 961 ms
76,004 KB
testcase_25 AC 962 ms
75,776 KB
testcase_26 AC 967 ms
75,584 KB
testcase_27 AC 1,294 ms
76,388 KB
testcase_28 AC 1,262 ms
77,288 KB
testcase_29 AC 1,292 ms
76,496 KB
testcase_30 AC 1,314 ms
76,548 KB
testcase_31 AC 1,256 ms
75,620 KB
testcase_32 AC 1,368 ms
75,852 KB
testcase_33 AC 1,225 ms
76,096 KB
testcase_34 AC 1,262 ms
77,412 KB
testcase_35 AC 1,249 ms
75,852 KB
testcase_36 AC 1,351 ms
76,024 KB
testcase_37 AC 1,348 ms
77,256 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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());}
    }
}
0