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

提出ソース

結果

問題	No.1600 Many Shortest Path Problems
ユーザー	chineristAC
提出日時	2021-07-10 01:12:24
言語	PyPy3 (7.3.15)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	12,531 bytes
コンパイル時間	252 ms
コンパイル使用メモリ	81,792 KB
実行使用メモリ	349,352 KB
最終ジャッジ日時	2024-07-01 20:09:46
合計ジャッジ時間	88,868 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	60 ms 59,520 KB
testcase_01	AC	59 ms 59,136 KB
testcase_02	AC	59 ms 59,264 KB
testcase_03	AC	61 ms 59,392 KB
testcase_04	TLE	-
testcase_05	AC	3,937 ms 348,436 KB
testcase_06	AC	58 ms 59,136 KB
testcase_07	AC	59 ms 59,008 KB
testcase_08	AC	59 ms 59,136 KB
testcase_09	AC	59 ms 59,392 KB
testcase_10	AC	1,325 ms 245,316 KB
testcase_11	AC	1,930 ms 257,828 KB
testcase_12	AC	3,120 ms 282,776 KB
testcase_13	AC	3,880 ms 325,276 KB
testcase_14	TLE	-
testcase_15	AC	59 ms 59,648 KB
testcase_16	AC	59 ms 59,392 KB
testcase_17	AC	3,520 ms 302,772 KB
testcase_18	AC	3,947 ms 349,352 KB
testcase_19	AC	70 ms 59,264 KB
testcase_20	AC	60 ms 59,392 KB
testcase_21	AC	3,606 ms 302,536 KB
testcase_22	AC	59 ms 59,648 KB
testcase_23	AC	59 ms 59,136 KB
testcase_24	TLE	-
testcase_25	AC	61 ms 59,264 KB
testcase_26	AC	60 ms 59,520 KB
testcase_27	AC	60 ms 59,648 KB
testcase_28	AC	60 ms 59,520 KB
testcase_29	AC	3,131 ms 308,000 KB
testcase_30	AC	3,102 ms 304,736 KB
testcase_31	AC	2,935 ms 297,244 KB
testcase_32	AC	2,997 ms 297,088 KB
testcase_33	AC	59 ms 59,264 KB
testcase_34	AC	59 ms 59,520 KB
testcase_35	AC	2,609 ms 347,560 KB
testcase_36	AC	2,072 ms 343,292 KB
testcase_37	AC	58 ms 59,776 KB
testcase_38	AC	2,300 ms 303,196 KB
testcase_39	AC	60 ms 59,648 KB
testcase_40	AC	3,105 ms 306,540 KB
testcase_41	AC	1,881 ms 299,696 KB
testcase_42	AC	2,073 ms 294,812 KB
testcase_43	AC	2,166 ms 297,616 KB
testcase_44	AC	2,525 ms 296,504 KB
testcase_45	AC	2,827 ms 309,204 KB
testcase_46	AC	2,807 ms 305,480 KB
testcase_47	AC	3,196 ms 307,440 KB
testcase_48	AC	3,420 ms 309,604 KB
testcase_49	AC	59 ms 59,136 KB
testcase_50	AC	58 ms 59,264 KB
testcase_51	AC	59 ms 59,136 KB
testcase_52	AC	59 ms 59,264 KB
testcase_53	AC	60 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.readline().rstrip()
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])
topo = []
while deq:
    v = deq.popleft()
    topo.append(v)
    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)

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))

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

        begin[nv] = next
        euler_tour.append(nv)
        next += 1
        stack.append(nv)
        appear[idx] = len(edge_on_path)
        edge_on_path.append(idx)
        for i,p,z in check_time[nv]:
            if appear[z]==-1:
                continue
            #print(edge_on_path)
            #print(nv,i,p,z)
            if rank[p] <= appear[z]:
                z_on_path[i] = nv

#print(z_on_path)

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)

alt_edge = [-1 for v in range(M)]
cnt = [0 for v in range(N)]
stack = [0]
seg = SegmentTree([M]*(2*N),min,M)
while stack:
    v = stack[-1]
    if cnt[v]==len(edge[v]):
        if v!=0:
            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
        stack.pop()
    else:
        nv,idx,c = edge[v][cnt[v]]
        cnt[v] += 1
        if nv==parent[v]:
            continue

        stack.append(nv)
        if alt[nv]:
            seg.update(begin[nv],alt[nv][-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

            check = lca(x,u)
            if check==x or lca(check,pv)==pv:

                res = dist(u,x) + dist(v,y) + cost
            else:
                res = dist(v,x) + dist(u,y) + cost
            res %= mod
            print(res)
    else:
        res = dist(x,y)
        print(res)

yukicoder

結果

テストケース

ソースコード