Submission #1098142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098142		vjudge1	Evacuation plan (IZhO18_plan)	Cpython 3	0 / 100	1676 ms	166792 KiB

plan

import sys
import heapq

sys.setrecursionlimit(10**6)

mxN = int(1e5) + 2
inf = int(1e9)
LG = 20

g = [[] for _ in range(mxN)]
adj = [[] for _ in range(mxN << 1)]
dist = [inf] * mxN
pa = list(range(mxN << 1))
dan = [0] * (mxN << 1)
vis = [False] * mxN
tin = [0] * (mxN << 1)
tout = [0] * (mxN << 1)
bl = [[0] * LG for _ in range(mxN << 1)]
edge = []
id = 0

def fp(x):
    if pa[x] == x:
        return x
    pa[x] = fp(pa[x])
    return pa[x]

def dfs(u, p):
    global id
    tin[u] = id = id + 1
    bl[u][0] = p
    for i in range(1, LG):
        bl[u][i] = bl[bl[u][i-1]][i-1]
    for v in adj[u]:
        if v == p:
            continue
        dfs(v, u)
    tout[u] = id

def check(u, v):
    return tin[u] <= tin[v] and tout[u] >= tout[v]

def lca(u, v):
    if check(u, v):
        return u
    if check(v, u):
        return v
    for i in range(LG-1, -1, -1):
        if not check(bl[u][i], v):
            u = bl[u][i]
    return bl[u][0]

def main():
    n, m = map(int, input().split())
    
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u].append((v, w))
        g[v].append((u, w))
        edge.append((w, u, v))
    
    k = int(input())
    a = list(map(int, input().split()))
    
    pq = []
    for e in a:
        dist[e] = 0
        heapq.heappush(pq, (0, e))
    
    while pq:
        d, u = heapq.heappop(pq)
        if vis[u]:
            continue
        vis[u] = True
        for v, w in g[u]:
            if not vis[v] and dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    
    for i in range(len(edge)):
        w, u, v = edge[i]
        edge[i] = (min(dist[u], dist[v]), u, v)
    
    edge.sort(reverse=True)
    
    pa = list(range(2 * mxN))
    c = n
    
    for w, u, v in edge:
        pu = fp(u)
        pv = fp(v)
        if pu == pv:
            continue
        c += 1
        dan[c] = w
        pa[pu] = pa[pv] = c
        adj[c].append(pu)
        adj[c].append(pv)
    
    dfs(c, c)
    
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(dan[lca(s, t)])

if __name__ == "__main__":
    main()

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46