結果

問題 No.1600 Many Shortest Path Problems
コンテスト
ユーザー chineristAC
提出日時 2021-07-10 02:19:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,103 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 463,980 KB
最終ジャッジ日時 2024-07-01 21:21:19
合計ジャッジ時間 83,875 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 SparseTable():
    def __init__(self,A,merge_func,ide_ele):
        N = len(A)
        n = N.bit_length()
        self.N = N
        self.n = n
        self.table=[[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func=merge_func

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=self.merge_func(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return self.merge_func(self.table[s][m],self.table[t-2**m+1][m])

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 = SparseTable(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)
    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)
0