結果

問題 No.3467 Bracket Warp
コンテスト
ユーザー kidodesu
提出日時 2026-02-28 15:52:08
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,826 ms / 2,000 ms
コード長 2,746 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 240 ms
コンパイル使用メモリ 78,364 KB
実行使用メモリ 180,848 KB
最終ジャッジ日時 2026-02-28 15:53:00
合計ジャッジ時間 40,893 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

S = input()
n = len(S)
A = [-1] * n
T = []
idx = 0
for i in range(n):
    s = S[i]
    if s == "(":
        t = 1
    else:
        t = 0
        if T and T[-1][0]:
            A[T[-1][1]] = idx
            A[i] = idx
            idx += 1
            T.pop()
            continue
    T.append((t, i))

m = n // 2
node = [[] for _ in range(m)]
C = set()
LOOP = [0] * (m+1)
Type = [0] * (m+1)
for i in range(n-1):
    if A[i] != A[i+1] and not (A[i], A[i+1]) in C:
        C.add((A[i], A[i+1]))
        C.add((A[i+1], A[i]))
        u, v = A[i], A[i+1]
        if S[i] == "(":
            node[u].append((v, 1))
            #node[v].append((u, -1))
        elif S[i+1] == "(":
            node[u].append((v, 0))
            node[v].append((u, 0))
        else:
            #node[u].append((v, -1))
            node[v].append((u, 2))

s = A[0]
D = [-1] * m
P = [[-1 for _ in range(m)] for _ in range(30)]
Dist = [[0 for _ in range(m)] for _ in range(30)]
W = [-1] * m
D[s] = 0
Z = [(-1, s, 1)]
while Y := Z:
    Z = []
    cnt = 0
    while X := Y:
        cnt += 1
        Y = []
        while X:
            pre, now, typ = X.pop()
            P[0][now] = pre
            Dist[0][now] = cnt
            LOOP[pre] += 1
            Type[now] = typ
            for nxt, f in node[now]:
                if D[nxt] != -1:
                    continue
                if not f:
                    D[nxt] = D[now]
                    Y.append((pre, nxt, typ))
                elif f == 1:
                    D[nxt] = D[now] + 1
                    Z.append((now, nxt, 1))
                else:
                    D[nxt] = D[now] + 1
                    Z.append((now, nxt, 2))

for i in range(1, 30):
    for j in range(m):
        P[i][j] = P[i-1][P[i-1][j]]
        Dist[i][j] = Dist[i-1][P[i-1][j]] + Dist[i-1][j]

def move(now, k):
    rep = 0
    i = 0
    while k:
        if k & 1:
            rep += Dist[i][now]
            now = P[i][now]
        k //= 2
        i += 1
    return now, rep

#print(P)
#print(Dist)

for _ in range(int(input())):
    l, r = list(map(lambda x: int(x)-1, input().split()))
    l, r = A[l], A[r]
    hl, hr = D[l], D[r]
    ans = 0
    if hl < hr:
        r, rep = move(r, hr-hl)
        ans += rep
    if hl > hr:
        l, rep = move(l, hl-hr)
        ans += rep
    for i in range(29, -1, -1):
        if P[i][l] != P[i][r]:
            ans += Dist[i][l]
            ans += Dist[i][r]
            l, r = P[i][l], P[i][r]
    p = P[0][l]
    if p == -1:
        print(ans + abs(Dist[0][l] - Dist[0][r]))
    else:
        if Type[l] == Type[r]:
            rep = abs(Dist[0][l] - Dist[0][r])
        else:
            rep = Dist[0][l] + Dist[0][r]
        rep = min(rep, LOOP[p]+1-rep)
        print(ans + rep)
0