結果

問題 No.2704 L to R Graph
ユーザー hirayuu_ychirayuu_yc
提出日時 2024-03-12 14:39:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,469 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,828 KB
実行使用メモリ 137,352 KB
最終ジャッジ日時 2024-09-29 22:19:21
合計ジャッジ時間 15,506 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
55,296 KB
testcase_01 AC 50 ms
60,928 KB
testcase_02 AC 43 ms
54,912 KB
testcase_03 AC 62 ms
67,840 KB
testcase_04 AC 61 ms
68,352 KB
testcase_05 AC 62 ms
68,096 KB
testcase_06 AC 62 ms
68,224 KB
testcase_07 AC 60 ms
68,352 KB
testcase_08 WA -
testcase_09 AC 649 ms
136,440 KB
testcase_10 WA -
testcase_11 AC 629 ms
134,528 KB
testcase_12 AC 581 ms
134,784 KB
testcase_13 AC 582 ms
134,284 KB
testcase_14 AC 570 ms
134,160 KB
testcase_15 AC 608 ms
134,168 KB
testcase_16 AC 579 ms
134,620 KB
testcase_17 AC 646 ms
134,284 KB
testcase_18 AC 656 ms
134,476 KB
testcase_19 AC 616 ms
134,352 KB
testcase_20 AC 642 ms
134,412 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 668 ms
134,288 KB
testcase_24 AC 711 ms
134,604 KB
testcase_25 AC 602 ms
134,164 KB
testcase_26 AC 631 ms
134,232 KB
testcase_27 AC 598 ms
136,932 KB
testcase_28 AC 556 ms
136,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from array import array
class UnionFind:
    def __init__(self,size:int)->None:
        self.siz=size
        self.tree=array("i",[-1]*size)
    
    def leader(self,pos:int)->int:
        ret=pos
        while self.tree[ret]>=0:
            ret=self.tree[ret]
        if pos!=ret:
            self.tree[pos]=ret
        return ret
    
    def same(self,u:int,v:int)->bool:
        return self.leader(u)==self.leader(v)
    
    def merge(self,u:int,v:int)->bool:
        u=self.leader(u)
        v=self.leader(v)
        if u==v:
            return False
        if self.tree[u]<self.tree[v]:
            u,v=v,u
        self.tree[v]+=self.tree[u]
        self.tree[u]=v
        return True
    
    def size(self,pos:int)->int:
        return -self.tree[self.leader(pos)]

    def groups(self)->list[list[int]]:
        mem=[[] for i in range(self.siz)]
        for i in range(self.siz):
            mem[self.leader(i)].append(i)
        ret=[]
        for i in mem:
            if len(i)!=0:
                ret.append(i)
        return ret

class DisjointSparseTable:
    def __init__(self,default:list,op,e=None):
        self.size=len(default)
        self.op=op
        self.e=e
        self.table=default*max(1,(self.size-1).bit_length())
        index=self.size
        for i in range(1,(self.size-1).bit_length()):
            for j in range(self.size):
                if ((j>>i)<<i)==j:
                    continue
                if (j>>i)&1:
                    self.table[j+index]=op(self.table[j-1+index],self.table[j+index])
                else:
                    pos=((j>>i)<<i)+((1<<i)-1)-(j&((1<<i)-1))
                    if pos<self.size:
                        self.table[pos+index]=op(self.table[pos+index],self.table[pos+1+index])
            index+=self.size
    
    def __getitem__(self,pos):
        if type(pos)==int:
            if not -self.size<=pos<self.size:
                raise IndexError
            if pos<0:
                return self.table[self.size+pos]
            else:
                return self.table[pos]
        left=pos.start
        if left==None:
            left=0
        right=pos.stop
        if right==None:
            right=self.size
        if not 0<=left<=right<=self.size:
            raise IndexError
        if left==right:
            return self.e()
        if left+1==right:
            return self.table[left]
        pos=((left^(right-1)).bit_length()-1)*self.size
        return self.op(self.table[pos+left],self.table[pos+right-1])

from collections import deque

def order_min(x,y):
    if srt[x]<srt[y]:
        return x
    return y

def lca(u,v):
    u=srt[u]
    v=srt[v]
    if u>v:
        u,v=v,u
    return dst[u:v+1]

N,L,R=map(int,input().split())
A=list(map(int,input().split()))
uni=UnionFind(N)
for i in range(N):
    A[i]-=1
    uni.merge(i,A[i])
cycle=[0]*N
giant=A[:]
for i in range(30):
    giant=[giant[giant[i]] for i in range(N)]
cycle_number=[-1]*N
for i in range(N):
    if cycle_number[giant[i]]!=-1:
        continue
    size=1
    cycle_number[giant[i]]=0
    pos=A[giant[i]]
    while cycle_number[pos]==-1:
        cycle_number[pos]=size
        pos=A[pos]
        size+=1
    cycle[uni.leader(i)]=size
for i in range(N):
    cycle[i]=cycle[uni.leader(i)]
tree=[[] for i in range(N+1)]
for i in range(N):
    if cycle_number[i]==-1:
        tree[A[i]].append(i)
    else:
        tree[N].append(i)
root=[0]*(N+1)
for i in tree[N]:
    root[i]=i
deep=[0]*(N+1)
tour=[]
srt=[-1]*(N+1)
vert=deque([N])
while vert:
    pos=vert.pop()
    if pos<0:
        tour.append(-pos-1)
        continue
    srt[pos]=len(tour)
    tour.append(pos)
    for i in tree[pos]:
        deep[i]=deep[pos]+1
        root[i]=max(root[i],root[pos])
        vert.append(-pos-1)
        vert.append(i)
dst=DisjointSparseTable(tour,order_min)
Q=int(input())
for i in range(Q):
    S,T=map(int,input().split())
    S-=1
    T-=1
    if not uni.same(S,T):
        print(-1)
        continue
    cyc=cycle[root[S]]
    dist=deep[S]-deep[T]+(cycle_number[root[T]]-cycle_number[root[S]])%cyc
    if cycle_number[T]==-1:
        if lca(S,T)!=T:
            print(-1)
            continue
        ans=(dist+R-1)//R
        if L*ans<=dist<=R*ans:
            print(ans)
        else:
            print(-1)
        continue
    fin=-1
    for i in range(400):
        ans=(dist+R-1)//R
        if L*ans<=dist<=R*ans:
            fin=ans
            break
        dist+=cyc
    print(fin)#todo:cycle
0