#677033 (PyPy3) No.1600 Many Shortest Path Problems

• 問題: No.1600 Many Shortest Path Problems
• ユーザー: chineristAC
• 提出日時: 2021-07-10 13:05:33
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 3,083 ms / 4,000 ms
• コード長: 17,560 bytes
• コンパイル時間: 316 ms
• コンパイル使用メモリ: 87,324 KB
• 実行使用メモリ: 339,512 KB
• 最終ジャッジ日時: 2023-09-14 18:54:30
• 合計ジャッジ時間: 77,277 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	112 ms; 73,644 KB
testcase_01	AC	115 ms; 73,808 KB
testcase_02	AC	119 ms; 73,980 KB
testcase_03	AC	115 ms; 73,388 KB
testcase_04	AC	2,915 ms; 336,304 KB
testcase_05	AC	2,957 ms; 338,600 KB
testcase_06	AC	120 ms; 73,484 KB
testcase_07	AC	118 ms; 73,732 KB
testcase_08	AC	115 ms; 73,384 KB
testcase_09	AC	114 ms; 73,812 KB
testcase_10	AC	1,152 ms; 243,416 KB
testcase_11	AC	1,711 ms; 261,668 KB
testcase_12	AC	2,632 ms; 273,000 KB
testcase_13	AC	3,083 ms; 313,204 KB
testcase_14	AC	2,999 ms; 339,512 KB
testcase_15	AC	120 ms; 73,804 KB
testcase_16	AC	117 ms; 73,504 KB
testcase_17	AC	2,984 ms; 298,136 KB
testcase_18	AC	2,863 ms; 336,396 KB
testcase_19	AC	117 ms; 73,512 KB
testcase_20	AC	116 ms; 73,512 KB
testcase_21	AC	3,069 ms; 291,552 KB
testcase_22	AC	117 ms; 73,508 KB
testcase_23	AC	117 ms; 73,928 KB
testcase_24	AC	2,961 ms; 335,356 KB
testcase_25	AC	121 ms; 73,572 KB
testcase_26	AC	116 ms; 73,736 KB
testcase_27	AC	116 ms; 73,924 KB
testcase_28	AC	115 ms; 73,936 KB
testcase_29	AC	2,395 ms; 290,800 KB
testcase_30	AC	2,651 ms; 291,092 KB
testcase_31	AC	2,417 ms; 291,092 KB
testcase_32	AC	2,518 ms; 287,452 KB
testcase_33	AC	119 ms; 73,516 KB
testcase_34	AC	117 ms; 73,752 KB
testcase_35	AC	1,961 ms; 336,604 KB
testcase_36	AC	1,607 ms; 328,912 KB
testcase_37	AC	119 ms; 73,736 KB
testcase_38	AC	1,843 ms; 290,916 KB
testcase_39	AC	117 ms; 73,744 KB
testcase_40	AC	2,559 ms; 292,048 KB
testcase_41	AC	1,653 ms; 283,784 KB
testcase_42	AC	1,784 ms; 279,196 KB
testcase_43	AC	2,196 ms; 288,116 KB
testcase_44	AC	2,289 ms; 285,140 KB
testcase_45	AC	2,267 ms; 291,436 KB
testcase_46	AC	2,403 ms; 293,980 KB
testcase_47	AC	2,670 ms; 294,156 KB
testcase_48	AC	2,837 ms; 295,380 KB
testcase_49	AC	118 ms; 73,648 KB
testcase_50	AC	118 ms; 73,564 KB
testcase_51	AC	118 ms; 73,392 KB
testcase_52	AC	117 ms; 73,752 KB
testcase_53	AC	118 ms; 73,776 KB

ソースコード

def divisors(M):
    d=[]
    i=1
    while M>=i**2:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    return d

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def eratosthenes(n):
    res=[0 for i in range(n+1)]
    prime=set([])
    for i in range(2,n+1):
        if not res[i]:
            prime.add(i)
            for j in range(1,n//i+1):
                res[i*j]=1
    return prime

def factorization(n):
    res=[]
    for p in prime:
        if n%p==0:
            while n%p==0:
                n//=p
            res.append(p)
    if n!=1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2,n+1):
        if x ** 2 > n:
            break
        if n%x==0:
            res = res//x * (x-1)
            while n%x==0:
                n //= x
    if n!=1:
        res = res//n * (n-1)
    return res

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

def isPrimeMR(n):
    if n==1:
        return 0
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p]+1):
                newres.append(d*p**j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):#排他的論理和の階乗
    if num==0:
        return 0
    elif num==1:
        return 1
    elif num==2:
        return 3
    elif num==3:
        return 0
    else:
        x=baseorder(num)
        return (2**x)*((num-2**x+1)%2)+function(num-2**x)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[digit[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[digit[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

def merge_sort(A,B):
    pos_A,pos_B = 0,0
    n,m = len(A),len(B)
    res = []
    while pos_A < n and pos_B < m:
        a,b = A[pos_A],B[pos_B]
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]]!=stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        self.group -= 1

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.size = n
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.segfunc(self.tree[2*k],self.tree[2*k+1])

    def query(self, l, r):
        if r==self.size:
            r = self.num

        res = self.ide_ele

        l += self.num
        r += self.num
        right = []
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                right.append(self.tree[r-1])
            l >>= 1
            r >>= 1

        for y in right[::-1]:
            res = self.segfunc(res,y)
        return res

class DualSegmentTree:
    def __init__(self, n, segfunc, ide_ele):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num

    def update(self,l,r,x):
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.tree[l] = self.segfunc(self.tree[l],x)
                l += 1
            if r & 1:
                self.tree[r-1] = self.segfunc(self.tree[r-1],x)
            l >>= 1
            r >>= 1

    def __getitem__(self,idx):
        idx += self.num
        res = self.ide_ele
        while idx:
            res = self.segfunc(res,self.tree[idx])
            idx>>=1
        return res

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.buffer.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

mod = 10**9 + 7

solver = random.randint(0,99)%2

if solver==0:
    N,M = mi()
    uf = UnionFindVerSize(N)
    E = []
    edge = [[] for v in range(N)]
    gomi = []
    cost = 2
    for i in range(M):
        u,v = mi()
        u,v = u-1,v-1
        E.append((u,v,i,cost))
        if not uf.is_same_group(u,v):
            uf.unite(u,v)
            edge[u].append((v,i,cost))
            edge[v].append((u,i,cost))
        else:
            gomi.append((u,v,i,cost))
        cost = 2 * cost % mod
    parent = [0 for v in range(N)]
    depth = [0 for v in range(N)]
    rank = [0 for v in range(N)]
    v_to_e = [-1 for i in range(N)]
    deq = deque([0])
    while deq:
        v = deq.popleft()
        for nv,idx,c in edge[v]:
            if nv==parent[v]:
                continue
            parent[nv] = v
            depth[nv] = (depth[v] + c) % mod
            rank[nv] = rank[v] + 1
            v_to_e[nv] = idx
            deq.append(nv)

    begin = [0 for v in range(N)]
    end = [0 for v in range(N)]
    cnt = [0 for v in range(N)]
    stack = [0]
    euler_tour = []
    while stack:
        v = stack[-1]
        euler_tour.append(v)
        if cnt[v] == len(edge[v]):
            end[v] = len(euler_tour) - 1
            stack.pop()
        else:
            nv,idx,c = edge[v][cnt[v]]
            cnt[v] += 1
            if nv==parent[v]:
                continue

            begin[nv] = len(euler_tour)
            stack.append(nv)

    init = [(rank[v]<<20)+v for v in euler_tour]
    seg_lca = SegmentTree(init,min,10**17)
    mask = 2**20-1

    def lca(u,v):
        l = min(begin[u],begin[v])
        r = max(end[u],end[v])
        r = seg_lca.query(l,r+1)
        p = r & mask
        return p

    def dist(x,y):
        p = lca(x,y)
        return (depth[x] + depth[y] - 2 * depth[p]) % mod

    Q = int(input())
    LCA = [-1 for v in range(Q)]
    query = []
    for _ in range(Q):
        x,y,z = mi()
        LCA[_] = lca(x-1,y-1)
        query.append((x-1,y-1,z-1))

    check_time = [[] for v in range(N)]
    for i in range(Q):
        x,y,z = query[i]
        p = LCA[i]
        check_time[x].append((i,p,z))
        check_time[y].append((i,p,z))

    alt = [[] for v in range(N)]
    for u,v,idx,c in gomi[::-1]:
        p = lca(u,v)

        while alt[u]:
            pre_idx,pre_p = alt[u][-1]
            if rank[pre_p] >= rank[p]:
                alt[u].pop()
            else:
                break
        alt[u].append((idx,p))

        while alt[v]:
            pre_idx,pre_p = alt[v][-1]
            if rank[pre_p] >= rank[p]:
                alt[v].pop()
            else:
                break
        alt[v].append((idx,p))

    delete_query = [[] for v in range(N)]
    for v in range(N):
        for idx,p in alt[v]:
            delete_query[p].append(v)


    z_on_path = [-1 for i in range(Q)]
    alt_edge = [-1 for v in range(M)]
    seg = SegmentTree([M]*len(euler_tour),min,M)
    edge_on_path = []
    appear = [-1 for i in range(M)]

    idx_on_alt = [len(alt[v])-1 for v in range(N)]
    for i in range(1,len(euler_tour)):
        v = euler_tour[i]
        if i==end[v]:
            if v!=0:
                appear[edge_on_path.pop()] = -1

                for cv in delete_query[v]:
                    idx_on_alt[cv] -= 1
                    k = idx_on_alt[cv]
                    if k!=-1:
                        seg.update(begin[cv],alt[cv][k][0])
                    else:
                        seg.update(begin[cv],M)

                e = v_to_e[v]
                res = seg.query(begin[v],end[v])
                if res!=M:
                    alt_edge[e] = res
        elif i==begin[v]:
            idx = v_to_e[v]
            appear[idx] = len(edge_on_path)
            edge_on_path.append(idx)
            for i,p,z in check_time[v]:
                if rank[p] <= appear[z]:
                    z_on_path[i] = v

            if alt[v]:
                seg.update(begin[v],alt[v][-1][0])

    for i in range(Q):
        x,y,z = query[i]
        p = LCA[i]
        if z_on_path[i]!=-1:
            if alt_edge[z]==-1:
                print(-1)
            else:
                u,v,idx,cost = E[alt_edge[z]]
                pu,pv,_,_ = E[z]
                if rank[pu] > rank[pv]:
                    pu,pv = pv,pu

                if z_on_path[i]==y:
                    x,y = y,x

                if begin[pv] <= begin[u] <= end[pv]:
                    res = dist(u,x) + dist(v,y) + cost
                else:
                    res = dist(v,x) + dist(u,y) + cost
                res %= mod
                print(res)
        else:
            res = (depth[x] + depth[y] - 2 * depth[p]) % mod
            print(res)

else:
    N,M = mi()
    uf = UnionFindVerSize(N)
    E = []
    edge = [[] for v in range(N)]
    gomi = []
    cost = 2
    for i in range(M):
        u,v = mi()
        u,v = u-1,v-1
        E.append((u,v,i,cost))
        if not uf.is_same_group(u,v):
            uf.unite(u,v)
            edge[u].append((v,i,cost))
            edge[v].append((u,i,cost))
        else:
            gomi.append((u,v,i,cost))
        cost = 2 * cost % mod

    parent = [0 for v in range(N)]
    depth = [0 for v in range(N)]
    rank = [0 for v in range(N)]
    v_to_e = [-1 for i in range(N)]
    deq = deque([0])
    while deq:
        v = deq.popleft()
        for nv,idx,c in edge[v]:
            if nv==parent[v]:
                continue
            parent[nv] = v
            depth[nv] = (depth[v] + c) % mod
            rank[nv] = rank[v] + 1
            v_to_e[nv] = idx
            deq.append(nv)

    begin = [0 for v in range(N)]
    end = [0 for v in range(N)]
    cnt = [0 for v in range(N)]
    stack = [0]
    euler_tour = [0]
    next = 1
    while stack:
        v = stack[-1]
        if cnt[v] == len(edge[v]):
            end[v] = next
            next += 1
            #print(v)
            euler_tour.append(v)
            stack.pop()
        else:
            nv,idx,c = edge[v][cnt[v]]
            cnt[v] += 1
            if nv==parent[v]:
                continue

            begin[nv] = next
            next += 1
            euler_tour.append(nv)
            stack.append(nv)


    LV = (N-1).bit_length()
    def construct(prv):
        kprv = [prv]
        S = prv
        for k in range(LV):
            T = [0]*N
            for i in range(N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            kprv.append(T)
            S = T
        return kprv

    kprv=construct(parent)

    def lca(u, v):
        dd = rank[v] - rank[u]
        if dd < 0:
            u, v = v, u
            dd = -dd

        # assert depth[u] <= depth[v]
        for k in range(LV+1):
            if dd & 1:
                v = kprv[k][v]
            dd >>= 1

        # assert depth[u] == depth[v]
        if u == v:
            return u

        for k in range(LV-1, -1, -1):
            pu = kprv[k][u]; pv = kprv[k][v]
            if pu != pv:
                u = pu; v = pv

        # assert kprv[0][u] == kprv[0][v]
        return kprv[0][u]

    def dist(x,y):
        p = lca(x,y)
        return (depth[x] + depth[y] - 2 * depth[p]) % mod

    Q = int(input())
    LCA = [-1 for v in range(Q)]
    query = []
    for _ in range(Q):
        x,y,z = mi()
        LCA[_] = lca(x-1,y-1)
        query.append((x-1,y-1,z-1))

    check_time = [[] for v in range(N)]
    for i in range(Q):
        x,y,z = query[i]
        p = LCA[i]
        check_time[x].append((i,p,z))
        check_time[y].append((i,p,z))

    alt = [[] for v in range(N)]
    for u,v,idx,c in gomi[::-1]:
        p = lca(u,v)

        while alt[u]:
            pre_idx,pre_p = alt[u][-1]
            if rank[pre_p] >= rank[p]:
                alt[u].pop()
            else:
                break
        alt[u].append((idx,p))

        while alt[v]:
            pre_idx,pre_p = alt[v][-1]
            if rank[pre_p] >= rank[p]:
                alt[v].pop()
            else:
                break
        alt[v].append((idx,p))

    delete_query = [[] for v in range(N)]
    for v in range(N):
        for idx,p in alt[v]:
            delete_query[p].append(v)


    z_on_path = [-1 for i in range(Q)]
    alt_edge = [-1 for v in range(M)]
    seg = SegmentTree([M]*(2*N),min,M)
    edge_on_path = []
    appear = [-1 for i in range(M)]
    for i in range(1,2*N):
        v = euler_tour[i]
        if i==end[v]:
            if v!=0:
                appear[edge_on_path.pop()] = -1

                for cv in delete_query[v]:
                    alt[cv].pop()
                    if alt[cv]:
                        seg.update(begin[cv],alt[cv][-1][0])
                    else:
                        seg.update(begin[cv],M)

                e = v_to_e[v]
                res = seg.query(begin[v],end[v])
                if res!=M:
                    alt_edge[e] = res
        else:
            idx = v_to_e[v]
            appear[idx] = len(edge_on_path)
            edge_on_path.append(idx)
            for i,p,z in check_time[v]:
                if rank[p] <= appear[z]:
                    z_on_path[i] = v

            if alt[v]:
                seg.update(begin[v],alt[v][-1][0])

    for i in range(Q):
        x,y,z = query[i]
        p = LCA[i]
        if z_on_path[i]!=-1:
            if alt_edge[z]==-1:
                print(-1)
            else:
                u,v,idx,cost = E[alt_edge[z]]
                pu,pv,_,_ = E[z]
                if rank[pu] > rank[pv]:
                    pu,pv = pv,pu

                if z_on_path[i]==y:
                    x,y = y,x

                if begin[pv] <= begin[u] <= end[pv]:
                    res = dist(u,x) + dist(v,y) + cost
                else:
                    res = dist(v,x) + dist(u,y) + cost
                res %= mod
                print(res)
        else:
            res = (depth[x] + depth[y] - 2 * depth[p]) % mod
            print(res)