Submission #123014

#	Time	Username	Problem	Language	Result	Execution time	Memory
123014		model_code	Valley (BOI19_valley)	Cpython 3	36 / 100	3043 ms	80904 KiB

valley

import sys
N, K, INF, W = 10**5+5, 17, 10**18, 200
sys.setrecursionlimit(N)

adj, cost = [[[] for i in range(N)] for j in range(2)]
is_shop, depth, root_dist, shop_dist = [[0 for i in range(N)] for j in range(4)]
st, par = [[[0 for i in range(N)] for j in range(K)] for k in range(2)]
n, s, q, e = [int(_) for _ in input().split()]
edges = []
def dfs(u, p = -1):
    shop_dist[u] = 0 if is_shop[u] else INF
    for i in range(len(adj[u])):
        v = adj[u][i]
        if v == p:
            continue
        par[0][v] = u
        depth[v] = depth[u]+1;
        root_dist[v] = root_dist[u]+cost[u][i]
        dfs(v,u)
        shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i])

def get_block(ind):
    u,v = edges[ind-1]
    return u if depth[u] > depth[v] else v
def prep_lca():
    for u in range(1,n+1):
        st[0][u] = min(shop_dist[u],shop_dist[par[0][u]])
    for s in range(1,K-1):
        for u in range(1,n+1):
            par[s][u] = par[s-1][par[s-1][u]]
            st[s][u] = min(st[s-1][u],st[s-1][par[s-1][u]])
def get_lca(u,v):
    if depth[u] < depth[v]:
        u,v = v,u
    for k in range(K-1,-1,-1):
        if depth[par[k][u]] >= depth[v]:
            u = par[k][u]
    if u == v:
        return u
    for k in range(K-1,-1,-1):
        if par[k][u] != par[k][v]:
            u, v = par[k][u], par[k][v]
    return par[0][u]
def solve(u, block):
    lca = get_lca(u,block)
    if lca != block:
        return "escaped";
    v = u
    ans = shop_dist[v]
    for k in range(K-1,-1,-1):
        if depth[par[k][v]] >= depth[block]:
            ans = min(ans,st[k][v])
            v = par[k][v]
    if ans == INF:
        return "oo"
    return ans + root_dist[u]
for i in range(n-1):
    a,b,w = [int(_) for _ in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    cost[a].append(w)
    cost[b].append(w)
    edges.append([a,b])
for i in range(s):
    is_shop[int(input())] = True
depth[e] = 1
dfs(e)
for i in range(1,n+1):
    if shop_dist[i] != INF:
        shop_dist[i] -= root_dist[i]
prep_lca()
for i in range(q):
    ind,u = [int(x) for x in input().split()]
    block = get_block(ind)
    print(solve(u,block))

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41