結果

問題 No.922 東北きりきざむたん
ユーザー neterukunneterukun
提出日時 2021-01-15 12:33:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,046 ms / 2,000 ms
コード長 6,861 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 87,116 KB
実行使用メモリ 174,344 KB
最終ジャッジ日時 2023-08-16 20:22:12
合計ジャッジ時間 21,528 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
71,420 KB
testcase_01 AC 76 ms
71,380 KB
testcase_02 AC 74 ms
71,320 KB
testcase_03 AC 75 ms
71,360 KB
testcase_04 AC 87 ms
71,388 KB
testcase_05 AC 82 ms
71,600 KB
testcase_06 AC 117 ms
77,568 KB
testcase_07 AC 88 ms
71,264 KB
testcase_08 AC 105 ms
76,236 KB
testcase_09 AC 592 ms
121,552 KB
testcase_10 AC 470 ms
100,472 KB
testcase_11 AC 576 ms
117,200 KB
testcase_12 AC 356 ms
113,296 KB
testcase_13 AC 317 ms
91,064 KB
testcase_14 AC 675 ms
141,200 KB
testcase_15 AC 232 ms
114,088 KB
testcase_16 AC 959 ms
166,616 KB
testcase_17 AC 970 ms
167,160 KB
testcase_18 AC 925 ms
167,980 KB
testcase_19 AC 936 ms
166,676 KB
testcase_20 AC 938 ms
167,932 KB
testcase_21 AC 953 ms
163,528 KB
testcase_22 AC 1,003 ms
167,384 KB
testcase_23 AC 1,031 ms
171,168 KB
testcase_24 AC 1,046 ms
174,344 KB
testcase_25 AC 804 ms
171,012 KB
testcase_26 AC 828 ms
172,088 KB
testcase_27 AC 797 ms
171,444 KB
testcase_28 AC 297 ms
124,932 KB
testcase_29 AC 694 ms
169,000 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class HLDecomposition:
    def __init__(self, tree):
        self.tree = tree
        self.n = len(tree)
        self.par = [-1] * self.n
        self.size = [1] * self.n
        self.depth = [0] * self.n
        self.preorder = [0] * self.n
        self.head = [i for i in range(self.n)]
        self.k = 0

        for v in range(self.n):
            if self.par[v] == -1:
                self.dfs_pre(v)
                self.dfs_hld(v)

    def __getitem__(self, v):
        return self.preorder[v]

    def dfs_pre(self, v):
        tree = self.tree
        stack = [v]
        order = [v]
        while stack:
            v = stack.pop()
            for chi_v in tree[v]:
                if chi_v == self.par[v]:
                    continue
                self.par[chi_v] = v
                self.depth[chi_v] = self.depth[v] + 1
                stack.append(chi_v)
                order.append(chi_v)

        for v in reversed(order):
            tree_v = tree[v]
            if len(tree_v) and tree_v[0] == self.par[v]:
                tree_v[0], tree_v[-1] = tree_v[-1], tree_v[0]
            for idx, chi_v in enumerate(tree_v):
                if chi_v == self.par[v]:
                    continue
                self.size[v] += self.size[chi_v]
                if self.size[chi_v] > self.size[tree_v[0]]:
                    tree_v[idx], tree_v[0] = tree_v[0], tree_v[idx]

    def dfs_hld(self, v):
        stack = [v]
        while stack:
            v = stack.pop()
            self.preorder[v] = self.k
            self.k += 1
            if len(self.tree[v]) == 0:
                continue
            top = self.tree[v][0]
            for chi_v in reversed(self.tree[v]):
                if chi_v == self.par[v]:
                    continue
                if chi_v == top:
                    self.head[chi_v] = self.head[v]
                else:
                    self.head[chi_v] = chi_v
                stack.append(chi_v)

    def lca(self, u, v):
        while u != -1 and v != -1:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.par[self.head[v]]
        return -1

    def distance(self, u, v):
        lca_uv = self.lca(u, v)
        if lca_uv == -1:
            return -1
        else:
            return self.depth[u] + self.depth[v] - 2 * self.depth[lca_uv]

    def range_vertex_path(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            l = max(self.preorder[self.head[v]], self.preorder[u])
            r = self.preorder[v]
            yield l, r + 1  # 半開区間
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return

    def range_edge_path(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.preorder[self.head[v]], self.preorder[v] + 1  # 半開区間
                v = self.par[self.head[v]]
            else:
                if u != v:
                    yield self.preorder[u] + 1, self.preorder[v]  + 1  # 半開区間 
                break

    def range_subtree(self, u):
        return self.preorder[u], self.preorder[u] + self.size[u]  # 半開区間[l, r)


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.n = n
        self.cnt = n

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parent[self.root(x)]

    def count(self):
        return self.cnt

    def groups(self):
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            res[self.root(i)].append(i)
        return [group for group in res if group]


def rerooting(n, edges, unit, merge, addnode):
    tree = [[] for i in range(n)]
    idxs = [[] for i in range(n)]
    for u, v in edges:
        idxs[u].append(len(tree[v]))
        idxs[v].append(len(tree[u]))
        tree[u].append(v)
        tree[v].append(u)
    sub = [[unit] * len(tree[v]) for v in range(n)]
    noderes = [unit] * n

    # topological sort
    tp_order = []
    par = [-1] * n
    for root in range(n):
        if par[root] != -1:
            continue
        stack = [root]
        while stack:
            v = stack.pop()
            tp_order.append(v)
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                par[nxt_v] = v
                stack.append(nxt_v)

    # tree DP
    for v in reversed(tp_order[1:]):
        res = unit
        par_idx = -1
        for idx, nxt_v in enumerate(tree[v]):
            if nxt_v == par[v]:
                par_idx = idx
                continue
            res = merge(res, sub[v][idx])
        if par_idx != -1:
            sub[par[v]][idxs[v][par_idx]] = addnode(res, v)

    # rerooting DP
    for v in tp_order:
        acc_back = [unit] * len(tree[v])
        for i in reversed(range(1, len(acc_back))):
            acc_back[i - 1] = merge(sub[v][i], acc_back[i])
        acc_front = unit
        for idx, nxt_v in enumerate(tree[v]):
            res = addnode(merge(acc_front, acc_back[idx]), v)
            sub[nxt_v][idxs[v][idx]] = res
            acc_front = merge(acc_front, sub[v][idx])
        noderes[v] = addnode(acc_front, v)
    return noderes


n, m, q = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
queries = [list(map(int, input().split())) for i in range(q)]


tree = [[] for i in range(n)]
uf = UnionFind(n)
for i, (u, v) in enumerate(edges):
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)
    uf.merge(u, v)
    edges[i] = (u, v)

ans = 0
weights = [0] * n
db = HLDecomposition(tree)
for u, v in queries:
    u -= 1
    v -= 1
    dist = db.distance(u, v)
    if dist == -1:
        weights[u] += 1
        weights[v] += 1
    else:
        ans += dist

unit = (0, 0)
merge = lambda x1, x2: (x1[0] + x2[0], x1[1] + x2[1])
addnode = lambda x1, v: (x1[0] + weights[v], x1[0] + x1[1])

res = rerooting(n, edges, unit, merge, addnode)
for gp in uf.groups():
    min_cost = 10 ** 9
    for i in gp:
        min_cost = min(res[i][1], min_cost)
    ans += min_cost
print(ans)
0