結果

問題 No.922 東北きりきざむたん
ユーザー tpynerivertpyneriver
提出日時 2019-11-09 20:33:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 929 ms / 2,000 ms
コード長 4,315 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 194,804 KB
最終ジャッジ日時 2024-09-15 04:49:42
合計ジャッジ時間 15,694 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
54,528 KB
testcase_01 AC 48 ms
54,400 KB
testcase_02 AC 47 ms
54,400 KB
testcase_03 AC 47 ms
54,528 KB
testcase_04 AC 74 ms
69,376 KB
testcase_05 AC 54 ms
57,216 KB
testcase_06 AC 112 ms
77,056 KB
testcase_07 AC 77 ms
70,656 KB
testcase_08 AC 90 ms
75,008 KB
testcase_09 AC 422 ms
137,536 KB
testcase_10 AC 326 ms
96,288 KB
testcase_11 AC 359 ms
125,716 KB
testcase_12 AC 354 ms
150,048 KB
testcase_13 AC 213 ms
93,356 KB
testcase_14 AC 557 ms
178,452 KB
testcase_15 AC 313 ms
154,332 KB
testcase_16 AC 825 ms
188,440 KB
testcase_17 AC 834 ms
188,640 KB
testcase_18 AC 815 ms
187,932 KB
testcase_19 AC 818 ms
187,308 KB
testcase_20 AC 838 ms
190,280 KB
testcase_21 AC 822 ms
179,048 KB
testcase_22 AC 787 ms
192,944 KB
testcase_23 AC 929 ms
188,384 KB
testcase_24 AC 918 ms
176,740 KB
testcase_25 AC 744 ms
158,820 KB
testcase_26 AC 761 ms
169,608 KB
testcase_27 AC 759 ms
185,396 KB
testcase_28 AC 358 ms
159,472 KB
testcase_29 AC 773 ms
194,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from copy import deepcopy
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

def getpar(Edge, p, par):
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, Q):
    L = []
    visited = set(Q)
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i in range(len(p) - 1):
        v = p[i]
        res[v].append(i)
    return res

def eulertour(Par, Cld, st):
    #P[par]にはNoneをいれる
    Cld = deepcopy(Cld)
    N = len(Cld)
    St = [None]*N
    En = [None]*N
    et = []
    sign = []
    vf = st
    cnt = 0
    depth = [0]*N
    while vf is not None:
        vn = vf
        et.append(vn)
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        cnt += 1
        if Cld[vn]:
            vf = Cld[vn].pop()
            sign.append(1)
            depth[vf] = depth[vn] + 1
        else:
            vf = P[vn]
            sign.append(-1)
    return St, En, et, sign[:-1], depth
        

N, M, Q = map(int, input().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

con = 0
used = set()
tp = [None]*N
vc = [None]*N

for i in range(N):
    if i in used:
        continue
    tp[con] = i
    vc[i] = con
    stack = [i]
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                vc[vf] = con
                stack.append(vf)
    con += 1

Tr = [[] for _ in range(con)]
pathq = []
P = [None]*N
cnum = [0]*N
knum = [0]*con
for tnum in range(con):
    P = getpar(Edge, tp[tnum], P)

for qu in range(Q):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    if vc[a] == vc[b]:
        pathq.append((a, b))
    else:
        cnum[a] += 1
        cnum[b] += 1
        knum[vc[a]] += 1
        knum[vc[b]] += 1

pars = [tp[i] for i in range(con)]
pset = set(pars)
L = topological_sort_tree(Edge, pars)

dp1 = [0]*N
dp2 = [0]*N
for l in L[::-1]:
    if l in pset:
        continue
    p = P[l]
    dp1[p] += cnum[l] + dp1[l]
    cnum[p] += cnum[l]

for l in L:
    if l in pset:
        dp2[l] = dp1[l]
        continue
    else:
        p = P[l]
        dp2[l] = dp2[p] + knum[vc[l]] - 2*cnum[l]


inf = 10**11
dp2min = [inf]*con
for i in range(N):
    dp2min[vc[i]] = min(dp2min[vc[i]], dp2[i])
ans = sum(dp2min)

P = [p if p is not None else N for p in P]
P.append(None)
C = getcld(P)

St, En, et, sign, depth = eulertour(P, C, N)
LCA = Segtree(et, None, initialize = True, segf = lambda x, y: x if y is None or (x is not None and depth[x] < depth[y]) else y)
dl = [None]*(N+1)
for i in range(len(et)):
    e = et[i]
    dl[e] = i
for a, b in pathq:
    da, db = dl[a], dl[b]
    if da > db:
        da, db = db, da
    lcaab = LCA.query(da, db + 1)
    ans += depth[a] + depth[b] - 2*depth[lcaab]
print(ans)
0