結果

問題 No.2704 L to R Graph
ユーザー hirayuu_ychirayuu_yc
提出日時 2024-03-12 07:38:01
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,255 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 136,916 KB
最終ジャッジ日時 2024-03-12 07:38:10
合計ジャッジ時間 9,459 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 AC 602 ms
136,060 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
    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
        print(dist)#todo:no_cycle
        continue
    if not uni.same(S,T):
        print(-1)
        continue
    print(dist)#todo:cycle
    assert False
0