#874028 (PyPy3) No.2325 Skill Tree

提出ソース

結果

問題	No.2325 Skill Tree
ユーザー	👑 amentorimaru
提出日時	2023-05-28 14:01:24
言語	PyPy3 (7.3.15)
結果	AC
実行時間	501 ms / 3,000 ms
コード長	11,413 bytes
コンパイル時間	174 ms
コンパイル使用メモリ	82,532 KB
実行使用メモリ	115,072 KB
最終ジャッジ日時	2024-12-26 22:53:58
合計ジャッジ時間	17,289 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	146 ms 91,136 KB
testcase_01	AC	146 ms 91,008 KB
testcase_02	AC	151 ms 91,520 KB
testcase_03	AC	150 ms 91,264 KB
testcase_04	AC	148 ms 91,264 KB
testcase_05	AC	150 ms 91,136 KB
testcase_06	AC	148 ms 91,136 KB
testcase_07	AC	249 ms 94,208 KB
testcase_08	AC	247 ms 100,224 KB
testcase_09	AC	267 ms 97,920 KB
testcase_10	AC	291 ms 106,112 KB
testcase_11	AC	290 ms 102,144 KB
testcase_12	AC	382 ms 113,536 KB
testcase_13	AC	393 ms 113,536 KB
testcase_14	AC	406 ms 113,536 KB
testcase_15	AC	394 ms 113,024 KB
testcase_16	AC	388 ms 113,408 KB
testcase_17	AC	356 ms 112,512 KB
testcase_18	AC	357 ms 112,384 KB
testcase_19	AC	367 ms 112,416 KB
testcase_20	AC	358 ms 112,256 KB
testcase_21	AC	359 ms 112,640 KB
testcase_22	AC	386 ms 114,944 KB
testcase_23	AC	390 ms 115,072 KB
testcase_24	AC	387 ms 114,944 KB
testcase_25	AC	397 ms 114,944 KB
testcase_26	AC	386 ms 114,560 KB
testcase_27	AC	501 ms 113,408 KB
testcase_28	AC	484 ms 113,128 KB
testcase_29	AC	484 ms 112,512 KB
testcase_30	AC	482 ms 113,152 KB
testcase_31	AC	477 ms 113,152 KB
testcase_32	AC	423 ms 112,896 KB
testcase_33	AC	434 ms 112,640 KB
testcase_34	AC	429 ms 113,000 KB
testcase_35	AC	477 ms 112,896 KB
testcase_36	AC	476 ms 112,768 KB
testcase_37	AC	483 ms 113,152 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from cmath import inf
from re import M
import sys
from collections import deque, Counter
from math import atan2, gcd, log10, pi, sqrt, ceil
from bisect import bisect, bisect_left, bisect_right, insort
from typing import Iterable, TypeVar, Union, Tuple, Iterator, List
# import bisect
from decimal import *
import fractions
import time
import copy
import heapq
import itertools
import bisect
import math
import random
from fractions import Fraction
from functools import lru_cache, partial, cmp_to_key
import operator
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
# import string
# import networkx as nx
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
mod2 = 998244353
# mod = 1 << 128
# mod = 10 ** 30 + 1
INF = 1 << 61
DIFF = 10 ** -9
DX = [1, 0, -1, 0, 1, 1, -1, -1]
DY = [0, 1, 0, -1, 1, -1, 1, -1]

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for _ in range(N)]

class UnionFind:
    def __init__(self,n):
        self.parent=list(range(n))
        self.size=[1]*n

    def root(self,a):
        if(self.parent[a]==a):return a
        self.parent[a]=self.root(self.parent[a])
        return self.parent[a]

    def union(self,a,b):
        pa=self.root(a)
        pb=self.root(b)
        if(pa==pb):return
        if(self.size[pa]>self.size[pb]):pa,pb=pb,pa
        self.parent[pa] = pb
        self.size[pb]+=self.size[pa]

    def same(self,a,b):
        return self.root(a)==self.root(b)

class Dijkstra:
    def __init__(self,n):
        self.dist=[inf]*n
        self.g = [list() for _ in range(n)]

    def add(self,u,v,c):
        self.g[u].append((v,c))

    def calc(self,s):
        self.dist[s]=0
        q = [(0,s)]
        while(len(q)>0):
            d,v0 = heapq.heappop(q)
            if(d>self.dist[v0]):continue
            for (v1,c) in self.g[v0]:
                if(self.dist[v1]<=d+c):continue
                self.dist[v1]=d+c
                heapq.heappush(q,(self.dist[v1],v1))

class SegTree:
    def __init__(self,n):
        self.size=1
        while(self.size<n):self.size*=2
        self.d=[self.unit()]*(self.size*2)
    def unit(self):
        return 0
    def calc(self,a,b):
        return a+b
    def set(self,i,v):
        self.forceset(i+self.size,v)
    def forceset(self,i,v):
        self.d[i]=v
        while(i>1):
            p=i//2
            self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])
            i=p
    #[l,r)
    def get(self,i):
        return self.d[self.size+i]
    def query(self,l,r):
        return self.queryImpl(l,r,0,self.size,1)
    def queryImpl(self,l,r,ll,rr,v):
        if(r<=ll or rr<=l):
            return self.unit()
        if(l<=ll and rr<=r):
            return self.d[v]
        m = (ll+rr)//2
        vl = self.queryImpl(l,r,ll,m,v*2+0)
        vr =self.queryImpl(l,r,m,rr,v*2+1)
        return self.calc(vl,vr)


class LazySegTree:
    def __init__(self,n):
        self.size=1
        while(self.size<n):self.size*=2
        self.d=[self.unit()]*(self.size*2)
        self.f=[self.id()]*self.size*2
    def unit(self):
        return -10**18
    def id(self):
        return -10**18
    def calc(self,a,b):
        return max(a,b)
    def set(self,i,v):
        self.forceset(i+self.size,v)
    def forceset(self,i,v):
        self.d[i]=v
        while(i>1):
            p=i//2
            self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])
            i=p
    #[l,r)
    def get(self,i):
        return self.query(i,i+1)
    def query(self,l,r):
        return self.queryImpl(l,r,0,self.size,1)
    def queryImpl(self,l,r,ll,rr,v):
        if(r<=ll or rr<=l):
            return self.unit()
        self.func(v)
        if(l<=ll and rr<=r):
            return self.d[v]
        m = (ll+rr)//2
        return self.calc(self.queryImpl(l,r,ll,m,v*2+0),self.queryImpl(l,r,m,rr,v*2+1))
    def funcSet(self,l,r,fnc):
        return self.funcSetImpl(l,r,fnc,0,self.size,1)
    def funcSetImpl(self,l,r,fnc,ll,rr,v):
        if(r<=ll or rr<=l):
            return
        if(l<=ll and rr<=r):
            self.comp(v,fnc)
            self.func(v)
            self.forceset(v,self.d[v])
            return
        m = (ll+rr)//2
        self.funcSetImpl(l,r,fnc,ll,m,v*2+0)
        self.funcSetImpl(l,r,fnc,m,rr,v*2+1)
        
    def func(self,i):
        if(i<self.size):
            self.comp(i*2+0,self.f[i])
            self.comp(i*2+1,self.f[i])
        self.d[i]=max(self.d[i],self.f[i])
        self.f[i]=self.id()        
    def comp(self,i,fnc):
        self.f[i]=max(self.f[i],fnc)

class BIT:
    def __init__(self,n):
        self.siz=1
        while(self.siz<n):self.siz<<=1
        self.b=[0]*self.siz
    
    def update(self,k,v):
        k+=1
        while(k<=self.siz):
            self.b[k-1]+=v
            k+=k&-k
    
    def query(self,k):
        r = 0
        k+=1
        while(k>0):
            r+=self.b[k-1]
            k-=k&-k
        return r

class MaxFlow:
    def __init__(self,n):
        self.g = [list() for _ in range(n)]
        self.r = [list() for _ in range(n)]
        self.f = [list() for _ in range(n)]
        self.mc=[False]*n
        self.size=n
        self.q=[-1]*n
        self.e=0

    def add(self,u,v,c):
        self.g[u].append(v)
        self.g[v].append(u)
        self.r[u].append(len(self.f[v]))
        self.r[v].append(len(self.f[u]))
        self.f[u].append(c)        
        self.f[v].append(0)
        self.e+=1        

    def bfs(self,s,t):
        self.depth=[-2]*self.size
        self.depth[s]=0
        self.q[0]=s
        l=0
        r=1
        while(l<r):
            v=self.q[l]
            l+=1
            for i in range(len(self.g[v])):
                v2=self.g[v][i]
                if(self.depth[v2]==-2 and self.f[v][i]>0):
                    self.depth[v2]=self.depth[v]+1
                    if(v2==t):return
                    self.q[r]=v2
                    r+=1

    def dfs(self,v,t,f):
        if(v==t):return f
        r=0
        for i in range(self.pg[v],len(self.g[v])):
            self.pg[v]=i
            v2=self.g[v][i]
            i2=self.r[v][i]
            if(self.f[v][i]==0 or self.depth[v]+1!=self.depth[v2]):continue
            d=self.dfs(v2,t,min(f-r,self.f[v][i]))
            if(d==0):continue
            self.f[v][i]-=d
            self.f[v2][i2]+=d
            r+=d
            if(r==f):break
        self.depth[v]=self.size
        return r
    def flow(self,s,t):
        r=0
        while(1):
            self.bfs(s,t)
            if(self.depth[t]==-2):return r 
            if(self.depth[t]*self.depth[t]*2>self.e):break
            self.pg=[0]*self.size
            f = self.dfs(s,t,10**18)
            if(f==0):break
            r+=f
        while(1):
            self.fi=[False]*self.size
            f = self.dfs2(s,t,10**18)
            if(f==0):break
            r+=f
        return r
    def mincut(self,v):
        self.mc[v]=True
        for i in range(len(self.g[v])):
            v2,c,i2=self.g[v][i]
            if(self.mc[v2] or self.f[v][i]==0):continue
            self.mincut(v2)

def extgcd(a,b):
    if(b==0):return (1,0)
    u,v=extgcd(b,a%b)
    return (v,u-a//b*v)

def convolution(f,g,m):
    l=1
    v=m-1
    r=v
    pg=3    
    if (m == 2):pg = 1;
    if (m == 754974721):pg=11;
    rpg=pow(pg,m-2,m)
    p=list()
    rp=list()
    while(len(f)+len(g)>l+1):
        l*=2
        r//=2    
    p.append(pow(pg,r,m))
    rp.append(pow(rpg,r,m))
    while(p[-1]!=1):
        p.append(p[-1]*p[-1]%m)
        rp.append(rp[-1]*rp[-1]%m)

    def FFT(ff,k,pl):
        fl=len(ff)
        if(fl==1):
            return ff
        hl=fl//2
        ef=FFT(ff[::2],k+1,pl)
        of=FFT(ff[1::2],k+1,pl)
        r=[0]*fl
        mul=1
        for i in range(hl):
            r[i+0]=(ef[i]+of[i]*mul)%m
            r[i+hl]=(ef[i]-of[i]*mul)%m
            mul=(mul*pl[k])%m
        return r
    ff=[0]*l
    gg=[0]*l
    for i in range(len(f)):
        ff[i]=f[i]
    for i in range(len(g)):
        gg[i]=g[i]
    ff=FFT(ff,0,p)
    gg=FFT(gg,0,p)
    for i in range(l):
        ff[i]=(ff[i]*gg[i])%m
    a=FFT(ff,0,rp)
    rl=pow(l,m-2,m)
    for i in range(l):
        a[i]=a[i]*rl%m
    return a

class scc:
    def __init__(self,n):
        self.g=[list() for _ in range(n)]
        self.rg=[list() for _ in range(n)]
        self.size=n
    def add(self,u,v):
        self.g[u].append(v)
        self.rg[v].append(u)
    def calc(self):
        f=[-1]*self.size
        nf=[0]
        c=[False]*self.size
        def dfs1(v):
            c[v]=True
            for tv in self.g[v]:
                if(c[tv]):continue
                dfs1(tv)
                f[nf[0]]=v
                nf[0]+=1
        for i in range(self.size):
            if(f[i]!=-1):continue
            dfs1(i)

        r=list()
        c=[False]*self.size
        nf[0]=0
        def dfs2(v):
            r[nf[0]].append(v)
            c[v]=True
            for tv in self.rg[v]:
                if(c[v]):continue
                dfs1(tv)
        for i in range(self.size-1,-1,-1):
            if(c[i]):continue
            r.append(list())
            dfs2(i)
            nf[0]+=1
        return r

def lower_bound(a,v):
    l=-1
    r=len(a)
    while(l+1<r):
        m=(l+r)//2
        if(a[m]<v):
            l=m
        else:
            r=m
    return r


class Bimatching:
    def __init__(self,n):
        self.size=n
        self.g=[[] for _ in range(n)]
        self.to=[-1]*n

    def add(self,u,v):
        self.g[u].append(v)

    def calc(self):
        p=range(self.size)
        c=[]
        for i in p:
            c.append((len(self.g[i]),i))
        c.sort()
        pl=[0]*self.size
        for i in p:
            pl[i]=c[i][1]

        rev=[-1]*self.size
        fr=[-1]*self.size
        q=[0]*self.size
        for i in pl:
            q[0]=i
            r=1
            d=[0]*self.size
            d[i]=1
            for l in p:
                if(l>=r):break
                v=q[l]
                for w in self.g[v]:
                    if(fr[w]!=-1):
                        if(d[fr[w]]==0):
                            d[fr[w]]=1
                            rev[fr[w]]=v
                            q[r]=fr[w]
                            r+=1
                    else:
                        r=0
                        vv=v
                        bw=w
                        for _ in p:
                            if(bw==-1):break
                            bw,self.to[vv]=self.to[vv],bw
                            fr[self.to[vv]]=vv
                            vv=rev[vv]
                        break


def main():
    n=int(input())
    lv=[10**18]*n
    l2=[10**18]*n
    lv[0]=0
    g=[list() for _ in range(n)]
    for v in range(n-1):
        l,a=read_values()
        a-=1
        l2[v+1]=l
        g[a].append(v+1)
    q=[0]
    while len(q)>0:
        v=q.pop()
        for v2 in g[v]:
            lv[v2]=max(l2[v2],lv[v])
            q.append(v2)
    slv=lv[:]
    slv.sort()
    q=int(input())
    for _ in range(q):
        t,x=read_values()
        if t==1:
            print(bisect.bisect_left(slv,x+1))
        else:
            if lv[x-1]>10**17:
                print(-1)
            else:
                print(lv[x-1])



    

if __name__ == "__main__":
    main()

yukicoder

結果

テストケース

ソースコード