結果

問題 No.2325 Skill Tree
ユーザー ゆうきゆうき
提出日時 2023-05-28 14:49:15
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,516 ms / 3,000 ms
コード長 8,578 bytes
コンパイル時間 2,908 ms
コンパイル使用メモリ 96,380 KB
実行使用メモリ 137,956 KB
最終ジャッジ日時 2023-08-27 10:39:22
合計ジャッジ時間 38,973 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
50,928 KB
testcase_01 AC 58 ms
51,076 KB
testcase_02 AC 58 ms
50,680 KB
testcase_03 AC 58 ms
50,784 KB
testcase_04 AC 59 ms
50,740 KB
testcase_05 AC 58 ms
50,920 KB
testcase_06 AC 58 ms
50,748 KB
testcase_07 AC 515 ms
69,516 KB
testcase_08 AC 538 ms
78,504 KB
testcase_09 AC 634 ms
82,084 KB
testcase_10 AC 641 ms
89,044 KB
testcase_11 AC 693 ms
87,028 KB
testcase_12 AC 1,005 ms
118,096 KB
testcase_13 AC 979 ms
119,648 KB
testcase_14 AC 1,060 ms
119,924 KB
testcase_15 AC 1,041 ms
114,752 KB
testcase_16 AC 887 ms
112,800 KB
testcase_17 AC 1,054 ms
112,572 KB
testcase_18 AC 1,060 ms
112,968 KB
testcase_19 AC 1,087 ms
112,892 KB
testcase_20 AC 1,197 ms
114,440 KB
testcase_21 AC 1,055 ms
113,060 KB
testcase_22 AC 746 ms
120,204 KB
testcase_23 AC 707 ms
126,556 KB
testcase_24 AC 737 ms
128,652 KB
testcase_25 AC 625 ms
112,444 KB
testcase_26 AC 749 ms
129,724 KB
testcase_27 AC 1,460 ms
137,796 KB
testcase_28 AC 1,359 ms
137,956 KB
testcase_29 AC 1,429 ms
134,648 KB
testcase_30 AC 1,415 ms
136,948 KB
testcase_31 AC 1,289 ms
136,412 KB
testcase_32 AC 1,516 ms
136,260 KB
testcase_33 AC 1,472 ms
134,060 KB
testcase_34 AC 1,494 ms
137,280 KB
testcase_35 AC 1,175 ms
136,900 KB
testcase_36 AC 1,148 ms
137,284 KB
testcase_37 AC 1,141 ms
136,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
//import static java.util.Collections.*;
//import static java.util.Comparator.*;

import java.awt.Point;

class Solver{
  static int infI = (int) 1e9;
  static long infL = (long) 1e18;
  //  static long mod = (int) 1e9 +7;
  static long mod = 998244353;
  static String yes = "Yes";
  static String no = "No";

  Util util = new Util();
  Random rd = ThreadLocalRandom.current();
  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };

  int N = in.it();
int[][] T = new int[N][];
  

int[] needLvl = new int[N];
List<Set<Integer>> list = new ArrayList<>();

  Object solve(){



for(int i = 1; i<N;i++)
  T[i] = new int[]{in.it(),in.idx()};

  int Q = in.it();
  int[][] qry = in.it(Q,2);

for(int i = 0; i<N;i++)
  list.add(new HashSet<>());

  for(int i = 1; i<N;i++)
    list.get(T[i][1]).add(i);

fill(needLvl,-1);
needLvl[0]=0;
Set<Integer> seen = new HashSet<>();
dfs(0, seen);

int[] sot = copyOf(needLvl,N);
sort(sot);
int ng =-1;
while(ng+1<N && sot[ng+1]<0)
 ng++;


for(var q : qry){
if(q[0] == 1){
int x = q[1];
  out.println(bSearchI(0,N,i-> sot[i]<=x)-ng);
}else{
log.println(q);
int y = q[1];
  out.println(needLvl[y-1]);
}
}

return null; }

void dfs(int p,Set<Integer> pars){
pars.add(p);

for(var i : list.get(p)){
if(pars.contains(i)){
needLvl[i]=-1;
}
needLvl[i] = Math.max(T[i][0],needLvl[p]);
dfs(i,pars);
}
pars.remove(p);

}

int bSearchI(int o,int n,Predicate<Integer> judge){
    for (int c = 0;1 < Math.abs(n -o);)
      if (judge.test(c = o +n >>1))
        o = c;
      else
        n = c;
    return o;
  }


  long bSearchL(long o,long n,Predicate<Long> judge){
    for (long c = 0;1 < Math.abs(n -o);)
      if (judge.test(c = o +n >>1))
        o = c;
      else
        n = c;
    return o;
  }

long pow(long x , long n){
x%=mod;
if(n==0)
return 1;
if(n==1)
return x;
return pow(x*x,n/2)*pow(x,n%2)%mod;
}
 

}

class Edge{
  int id;
  int u;
  int v;
  long l;
  Edge rev;

  Edge(int id,int u,int v){
    this.id = id;
    this.u = u;
    this.v = v;
  }

  void rev(Edge rev){ rev.l = l; }

}

class Util{
  long st = System.currentTimeMillis();

  long elapsed(){ return System.currentTimeMillis() -st; }

  static int[][] trans(int[]... T){ return arr(new int[T[0].length][],i -> arrI(T.length,j -> T[j][i])); }

  static int[][] addId(int[][] T){
    return arr(new int[T.length][],i -> {
      int[] t = copyOf(T[i],T[i].length +1);
      t[t.length -1] = i;
      return t;
    });
  }

  static long[][] trans(long[]... T){ return arr(new long[T[0].length][],i -> arrL(T.length,j -> T[j][i])); }

  static double[][] trans(double[]... T){ return arr(new double[T[0].length][],i -> arrD(T.length,j -> T[j][i])); }

  static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

}

class MyReader{
  byte[] buf = new byte[1 <<16];
  int ptr = 0;
  int tail = 0;
  InputStream in;

  MyReader(InputStream in){ this.in = in; }

  byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  boolean isPrintable(byte c){ return 32 < c && c < 127; }

  boolean isNum(byte c){ return 47 < c && c < 58; }

  byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  int it(){ return Math.toIntExact(lg()); }

  int[] it(int N){ return Util.arrI(N,i -> it()); }

  int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  int idx(){ return it() -1; }

  int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  int[][] qry(int Q){ return Util.arr(new int[Q][],i -> new int[]{idx(), idx(), i}); }

  long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  double dbl(){ return Double.parseDouble(str()); }

  double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  char[] ch(){ return str().toCharArray(); }

  char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  String line(){
    StringBuilder sb = new StringBuilder();

    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());

    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  String[] str(int N){ return Util.arr(new String[N],i -> str()); }

  Edge[] e(int N,int M){ return e(N,M,e -> e.l = 1); }

  Edge[] e(int N,int M,Consumer<Edge> f){
    return Util.arr(new Edge[M],i -> {
      Edge e = new Edge(i,idx(),idx());
      f.accept(e);
      return e;
    });
  }

  Edge[][] g(int N,int M,boolean b){ return g(N,b,e(N,M)); }

  Edge[][] g(int N,int M,boolean b,Consumer<Edge> f){ return g(N,b,e(N,M,f)); }

  Edge[][] g(int N,boolean b,Edge[] E){
    int[] c = new int[N];

    for (Edge e:E) {
      c[e.u]++;
      if (!b)
        c[e.v]++;
    }

    Edge[][] g = Util.arr(new Edge[N][],i -> new Edge[c[i]]);

    for (Edge e:E) {

      g[e.u][--c[e.u]] = e;
      if (!b) {
        Edge rev = new Edge(e.id,e.v,e.u);
        e.rev(rev);
        g[e.v][--c[e.v]] = e.rev = rev;
      }
    }
    return g;
  }
}

class MyWriter{
  OutputStream out;
  byte[] buf = new byte[1 <<16];
  byte[] ibuf = new byte[20];
  int tail = 0;

  MyWriter(OutputStream out){ this.out = out; }

  void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private void sp(){ write((byte) ' '); }

  protected void ln(){ write((byte) '\n'); }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(byte[] b,int off,int len){
    for (int i = off;i < off +len;i++)
      write(b[i]);
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }

    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);

    write(ibuf,i,ibuf.length -i);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Solver.yes : Solver.no);
    else if (obj instanceof Character)
      write((byte) (char) obj);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj instanceof Collection<?>) {
      Iterator<?> itr = ((Collection<?>) obj).iterator();
      while (itr.hasNext()) {
        print(itr.next());
        if (itr.hasNext())
          ln();
      }
    } else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      boolean ln = false;

      if (0 < l) {
        Object a = Array.get(obj,0);
        ln = !(a instanceof char[]) && a.getClass().isArray();
      }
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          if (ln)
            ln();
          else
            sp();
      }
    } else
      for (char b:Objects.toString(obj).toCharArray())
        write((byte) b);
  }

  void println(Object obj){
    if (obj == null)
      return;
    print(obj);
    ln();
  }
}

class Main{
  public static void main(String[] args) throws Exception{
    Solver solver = new Solver();
    Optional.ofNullable(solver.solve()).ifPresent(solver.out::println);
    solver.out.flush();
    solver.log.println(solver.util.elapsed());
  }
}
0