結果

問題 No.2704 L to R Graph
ユーザー hirayuu_yc
提出日時 2024-03-12 15:26:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 851 ms / 3,000 ms
コード長 7,363 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 82,480 KB
実行使用メモリ 143,360 KB
最終ジャッジ日時 2024-09-29 22:20:25
合計ジャッジ時間 16,987 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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
class FoldableDeque:
    def __init__(self,op,e)->None:
        self.op=op
        self.e=e
        self.left=deque()
        self.leftop=deque([e()])
        self.right=deque()
        self.rightop=deque([e()])
    
    def append(self,v:any)->None:
        self.right.append(v)
        self.rightop.append(self.op(self.rightop[-1],v))
    def appendleft(self,v:any)->None:
        self.left.append(v)
        self.leftop.append(self.op(v,self.leftop[-1]))
    
    def pop(self)->any:
        if len(self.right)==0:
            nl=[]
            while len(self.left)>0:
                nl.append(self.popleft())
            self.leftop=deque([self.e()])
            half=len(nl)//2
            for i in nl[half:]:
                self.append(i)
            for i in nl[:half][::-1]:
                self.appendleft(i)
        self.rightop.pop()
        return self.right.pop()
    
    def popleft(self)->any:
        if len(self.left)==0:
            nr=[]
            while len(self.right)>0:
                nr.append(self.pop())
            self.rightop=deque([self.e()])
            half=len(nr)//2
            for i in nr[half:]:
                self.appendleft(i)
            for i in nr[:half][::-1]:
                self.append(i)
        self.leftop.pop()
        return self.left.pop()
    def get_all(self):
        return self.op(self.leftop[-1],self.rightop[-1])
    
    def __len__(self)->int:
        return len(self.left)+len(self.right)
    def __str__(self)->str:
        return str(list(self.left)[::-1])+str(list(self.right))
class FoldableQueue(FoldableDeque):
    def pop(self):
        assert False
    def popleft(self)->any:
        if len(self.left)==0:
            for i in reversed(self.right):
                self.appendleft(i)
            self.right=deque()
            self.rightop=deque([self.e()])
        self.leftop.pop()
        return self.left.pop()
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]
INF=(1<<61)-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
cycles_size=[0]*(N+1)
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
    cycles_size[size]=uni.size(i)
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)
dps=[[] for i in range(N+1)]
for i in range(N+1):
    if cycles_size[i]==0:
        continue
    dp=[INF]*cycles_size[i]
    seg=[INF]*(i*4)
    for j in range(i+1):
        lf=L*j
        ri=R*j+1
        if ri-lf>=i:
            seg[1]=min(seg[1],j)
            break
        lf%=i
        ri%=i
        if lf>=ri:
            ri+=i
        lf+=i*2
        ri+=i*2
        while lf<ri:
            if lf&1:
                seg[lf]=min(seg[lf],j)
                lf+=1
            if ri&1:
                ri-=1
                seg[ri]=min(seg[ri],j)
            lf>>=1
            ri>>=1
    for j in range(i*2):
        pos=j+i*2
        while pos>0:
            dp[j%i]=min(dp[j%i],seg[pos])
            pos>>=1
    que=FoldableQueue(min,lambda:INF)
    for j in range(R,L-1,-1):
        que.append(dp[(-j)%i])
    for j in range(i,cycles_size[i]):
        dp[j]=que.get_all()+1
        que.popleft()
        que.append(dp[max(j+1-L,(j+1-L)%i)])
    for j in range(cycles_size[i]):
        if dp[j]>=INF:
            dp[j]=-1
    dps[i]=dp
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
    print(dps[cyc][dist])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0