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

提出ソース

結果

問題	No.1600 Many Shortest Path Problems
ユーザー	chineristAC
提出日時	2021-07-10 02:12:17
言語	PyPy3 (7.3.15)
結果	AC
実行時間	3,668 ms / 4,000 ms
コード長	11,620 bytes
コンパイル時間	156 ms
コンパイル使用メモリ	82,464 KB
実行使用メモリ	344,236 KB
最終ジャッジ日時	2024-07-01 21:13:34
合計ジャッジ時間	76,810 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	52 ms 59,136 KB
testcase_01	AC	52 ms 58,624 KB
testcase_02	AC	53 ms 58,752 KB
testcase_03	AC	51 ms 59,264 KB
testcase_04	AC	2,988 ms 344,236 KB
testcase_05	AC	3,004 ms 343,528 KB
testcase_06	AC	52 ms 58,880 KB
testcase_07	AC	52 ms 59,136 KB
testcase_08	AC	51 ms 58,880 KB
testcase_09	AC	53 ms 59,520 KB
testcase_10	AC	1,290 ms 244,260 KB
testcase_11	AC	1,700 ms 256,196 KB
testcase_12	AC	2,746 ms 271,536 KB
testcase_13	AC	3,207 ms 308,048 KB
testcase_14	AC	3,058 ms 342,728 KB
testcase_15	AC	53 ms 59,392 KB
testcase_16	AC	53 ms 59,392 KB
testcase_17	AC	3,022 ms 292,032 KB
testcase_18	AC	3,066 ms 343,476 KB
testcase_19	AC	53 ms 59,264 KB
testcase_20	AC	53 ms 59,648 KB
testcase_21	AC	3,161 ms 293,840 KB
testcase_22	AC	55 ms 59,264 KB
testcase_23	AC	56 ms 58,880 KB
testcase_24	AC	3,179 ms 343,296 KB
testcase_25	AC	55 ms 59,520 KB
testcase_26	AC	55 ms 59,264 KB
testcase_27	AC	53 ms 59,264 KB
testcase_28	AC	52 ms 59,648 KB
testcase_29	AC	2,309 ms 294,644 KB
testcase_30	AC	2,883 ms 297,928 KB
testcase_31	AC	2,438 ms 290,156 KB
testcase_32	AC	2,565 ms 290,944 KB
testcase_33	AC	52 ms 59,264 KB
testcase_34	AC	53 ms 59,520 KB
testcase_35	AC	1,900 ms 338,148 KB
testcase_36	AC	1,594 ms 335,640 KB
testcase_37	AC	52 ms 59,520 KB
testcase_38	AC	1,797 ms 289,436 KB
testcase_39	AC	53 ms 59,136 KB
testcase_40	AC	2,963 ms 299,168 KB
testcase_41	AC	1,670 ms 281,732 KB
testcase_42	AC	2,009 ms 284,964 KB
testcase_43	AC	2,204 ms 287,680 KB
testcase_44	AC	2,423 ms 287,048 KB
testcase_45	AC	2,329 ms 292,512 KB
testcase_46	AC	2,425 ms 292,756 KB
testcase_47	AC	3,668 ms 305,540 KB
testcase_48	AC	2,969 ms 296,728 KB
testcase_49	AC	52 ms 58,624 KB
testcase_50	AC	53 ms 59,008 KB
testcase_51	AC	53 ms 58,752 KB
testcase_52	AC	52 ms 59,264 KB
testcase_53	AC	52 ms 59,264 KB

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

ソースコード

raw source code

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

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)]
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]:
                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
    elif i==begin[v]:
        #assert 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)

yukicoder

結果

テストケース

ソースコード