結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー tpyneriver
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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