鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）E,F,G問題メモ

from collections import defaultdict


def solve(n, matrix):
    INF = 1 << 60
    ans = [[INF] * n for _ in range(n)]
    for i in range(n):
        ans[i][i] = 0

    links = defaultdict(list)
    for i, row in enumerate(matrix):
        for j, c in enumerate(row):
            if c == '-':
                continue
            links[c].append((i, j))
            if i != j:
                ans[i][j] = 1
    links = dict(links)

    for _ in range(100):
        updated = False
        for edges in links.values():
            m = len(edges)
            for i in range(m):
                a, b = edges[i]
                for j in range(i + 1, m):
                    c, d = edges[j]
                    if ans[a][d] > ans[b][c] + 2:
                        ans[a][d] = ans[b][c] + 2
                        updated = True
                    elif ans[c][b] > ans[d][a] + 2:
                        ans[c][b] = ans[d][a] + 2
                        updated = True
        if not updated:
            break
    for i in range(n):
        for j in range(n):
            if ans[i][j] == INF:
                ans[i][j] = -1
    return ans


n = int(input())
matrix = [input() for _ in range(n)]
ans = solve(n, matrix)
for row in ans:
    print(*row)

def solve(n, edges):
    edges = [(a - 1, b - 1) for a, b in edges]
    links = [set() for _ in range(n)]
    for a, b in edges:
        links[a].add(b)
        links[b].add(a)

    if all(len(l) < 4 for l in links):
        return -1

    dp = [-1] * n
    q = [0]
    ans = 0
    while q:
        u = q[-1]
        if dp[u] == -1:
            dp[u] = -2
            for v in links[u]:
                links[v].remove(u)
                q.append(v)
            continue
        q.pop()

        if len(links[u]) >= 3:
            children = [dp[v] for v in links[u]]
            children.sort(reverse=True)
            if len(children) >= 4:
                ans = max(ans, sum(children[:4]) + 1)
            elif len(children) >= 3:
                ans = max(ans, sum(children[:3]) + 1)
            dp[u] = sum(children[:3]) + 1
        else:
            dp[u] = 0

    return ans * 3 + 2


n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
ans = solve(n, edges)
print(ans)

from bisect import bisect


class PartialPersistentUnionFind:
    """
    時刻 t は、「t番目のuniteクエリ完了時点」を意味する。初期状態は t=0。

    root(x [, t]): 時刻 t の x の根（t 省略時は最新）
    find(x, y [, t]): 時刻 t に x と y が同一グループか判定
    unite(x, y): x と y を結合
    get_size(x [, t]): 時刻 t の x の属するグループの要素数
    """

    def __init__(self, n: int):
        self.t = 0
        self.timetable = [[0] for _ in range(n)]
        self.valuetable = [[-1] for _ in range(n)]

    def _getvalue(self, x: int, t: int):
        i = bisect(self.timetable[x], t) - 1
        return self.valuetable[x][i]

    def root(self, x: int, t: int = -1):
        # 更新が行われるのは、その時点の根に対してだけなので、
        # x の最終更新時刻 > t なら、t 時点では確実に x は根。
        # そうでない場合は最終更新時の値の正負で、通常のUnionFindと同様、根か、親を持っているか判別。
        if t == -1:
            t = self.t
        while self.timetable[x][-1] <= t and self.valuetable[x][-1] >= 0:
            x = self.valuetable[x][-1]
        return x

    def is_same(self, x: int, y: int, t: int = -1):
        return self.root(x, t) == self.root(y, t)

    def unite(self, x: int, y: int):
        self.t += 1
        r1 = self.root(x, self.t)
        r2 = self.root(y, self.t)
        if r1 == r2:
            return False
        self.timetable[r1].append(self.t)
        self.timetable[r2].append(self.t)
        d1 = self.valuetable[r1][-1]
        d2 = self.valuetable[r2][-1]
        if d1 <= d2:
            self.valuetable[r1].append(d1 + d2)
            self.valuetable[r2].append(r1)
        else:
            self.valuetable[r1].append(r2)
            self.valuetable[r2].append(d1 + d2)
        return True

    def get_size(self, x: int, t: int = -1):
        if t == -1:
            t = self.t
        r = self.root(x, t)
        return -self._getvalue(r, t)


def solve(h, w, field, q, queries):
    edges = []
    for i in range(h):
        for j in range(w):
            if i > 0:
                edges.append((min(field[i - 1][j], field[i][j]), (i - 1) * w + j, i * w + j))
            if j > 0:
                edges.append((min(field[i][j - 1], field[i][j]), i * w + j - 1, i * w + j))
    edges.sort(reverse=True)
    # print(edges)

    uft = PartialPersistentUnionFind(h * w)
    for _, u, v in edges:
        uft.unite(u, v)

    ans = []
    for a, b, y, c, d, z in queries:
        s = (a - 1) * w + (b - 1)
        g = (c - 1) * w + (d - 1)
        if s == g:
            ans.append(abs(y - z))
            continue
        l = 0
        r = len(edges)
        while l + 1 < r:
            m = (l + r) // 2
            # print(f'{s=} {g=} {l=} {r=} {m=} {uft.is_same(s,g,m)=}')
            if uft.is_same(s, g, m):
                r = m
            else:
                l = m

        min_f = edges[l][0]
        if min(y, z) <= min_f:
            ans.append(abs(y - z))
        else:
            ans.append(y + z - min_f * 2)

    return ans


h, w = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(h, w, field, q, queries)
print('\n'.join(map(str, ans)))