結果

問題 No.3148 Min-Cost Destruction of Parentheses
コンテスト
ユーザー naniwazu
提出日時 2025-05-08 06:26:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,064 ms / 4,000 ms
コード長 2,178 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 96,256 KB
最終ジャッジ日時 2025-05-15 23:07:27
合計ジャッジ時間 19,615 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heapify, heappop, heappush


# UnionFindを改造
class UnionFind:
    def __init__(self, A):
        self.N = len(A)
        self.parents = [-1] * self.N
        self.zeros = A
        self.ones = [1] * self.N
        self.ans = 0

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            st = []
            while self.parents[x] >= 0:
                st.append(x)
                x = self.parents[x]
            for y in st:
                self.parents[y] = x
            return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.ans += self.ones[x] * self.zeros[y]
        self.zeros[x] += self.zeros[y]
        self.ones[x] += self.ones[y]

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.N) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group = {r: [] for r in self.roots()}
        for i in range(self.N):
            group[self.find(i)].append(i)
        return group

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


N = int(input())
S = input()
A = [0] + list(map(int, input().split()))

uf = UnionFind(A)

stack = [0]
parent = [-1] * (N + 1)
next_idx = 1
for i in range(2 * N):
    if S[i] == "(":
        parent[next_idx] = stack[-1]
        stack.append(next_idx)
        next_idx += 1
    else:
        stack.pop()

q = [(-A[i], i) for i in range(N + 1)]
heapify(q)

while q:
    value, idx = heappop(q)
    if value != -uf.zeros[idx] / uf.ones[idx]:
        continue
    uf.union(parent[idx], idx)
    new_head = uf.find(idx)
    if new_head != 0:
        heappush(q, (-uf.zeros[new_head] / uf.ones[new_head], new_head))

print(uf.ans)
0