結果

問題 No.922 東北きりきざむたん
ユーザー roarisroaris
提出日時 2020-12-02 15:20:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 736 ms / 2,000 ms
コード長 4,010 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 120,376 KB
最終ジャッジ日時 2024-09-13 10:13:09
合計ジャッジ時間 13,217 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
56,236 KB
testcase_01 AC 42 ms
55,868 KB
testcase_02 AC 41 ms
55,136 KB
testcase_03 AC 43 ms
55,224 KB
testcase_04 AC 51 ms
63,728 KB
testcase_05 AC 48 ms
62,188 KB
testcase_06 AC 61 ms
69,216 KB
testcase_07 AC 52 ms
64,788 KB
testcase_08 AC 56 ms
67,628 KB
testcase_09 AC 313 ms
100,236 KB
testcase_10 AC 279 ms
84,128 KB
testcase_11 AC 342 ms
94,848 KB
testcase_12 AC 233 ms
107,224 KB
testcase_13 AC 170 ms
84,392 KB
testcase_14 AC 430 ms
113,152 KB
testcase_15 AC 184 ms
110,976 KB
testcase_16 AC 602 ms
114,468 KB
testcase_17 AC 605 ms
115,592 KB
testcase_18 AC 591 ms
113,192 KB
testcase_19 AC 616 ms
114,404 KB
testcase_20 AC 617 ms
113,768 KB
testcase_21 AC 592 ms
111,744 KB
testcase_22 AC 583 ms
111,872 KB
testcase_23 AC 734 ms
119,504 KB
testcase_24 AC 736 ms
119,472 KB
testcase_25 AC 638 ms
119,496 KB
testcase_26 AC 628 ms
119,268 KB
testcase_27 AC 630 ms
120,376 KB
testcase_28 AC 197 ms
116,908 KB
testcase_29 AC 456 ms
116,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

class LCA:
    def __init__(self, N, G):
        self.N = N
        self.G = G
        self.log_size = 22
        self.par = [[-1]*self.N for _ in range(self.log_size)]
        self.dep = [-1]*self.N
        
        for i in range(self.N):
            if self.dep[i]==-1:
                self.dep[i] = 0
                q = deque([i])
                
                while q:
                    v = q.popleft()
                    
                    for nv in self.G[v]:
                        if self.dep[nv]==-1:
                            self.par[0][nv] = v
                            self.dep[nv] = self.dep[v]+1
                            q.append(nv)
                    
        for i in range(1, self.log_size):
            for v in range(self.N):
                if self.par[i-1][v]>=0:
                    self.par[i][v] = self.par[i-1][self.par[i-1][v]]
        
    def lca(self, u, v):
        if self.dep[u]>self.dep[v]:
            u, v = v, u
        
        for i in range(self.log_size):
            if ((self.dep[v]-self.dep[u])>>i)&1:
                v = self.par[i][v]
        
        if u==v:
            return u
        
        for i in range(self.log_size-1, -1, -1):
            if self.par[i][u]!=self.par[i][v]:
                u, v = self.par[i][u], self.par[i][v]
        
        return self.par[0][u]
    
    def dist(self, u, v):
        return self.dep[u]+self.dep[v]-2*self.dep[self.lca(u, v)]

def dfs1(s):
    in_order_now = 0
    stack = [(s, -1, 0)]
    total_d = 0
    vs = []
    
    while stack:
        v, pv, d = stack.pop()
        
        in_order[v] = in_order_now
        in_order_now += 1
        total_d += cnt[v]*d
        vs.append((in_order[v], v))
        
        for nv in G[v]:
            if nv==pv:
                continue
            
            par[nv] = v
            stack.append((nv, v, d+1))
    
    vs.sort(reverse=True)
    
    for _, v in vs:
        if v==s:
            continue
        
        cnt[par[v]] += cnt[v]
    
    return total_d
    
def dfs2(s, total_d):
    stack = [(s, -1, total_d)]
    res = total_d
    
    while stack:
        v, pv, total_d = stack.pop()
        
        for nv in G[v]:
            if nv==pv:
                continue
            
            next_d = total_d+cnt[s]-2*cnt[nv]
            res = min(res, next_d)
            stack.append((nv, v, next_d))
    
    return res
    
N, M, Q = map(int, input().split())
uf = Unionfind(N)
G = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    uf.unite(u-1, v-1)
    G[u-1].append(v-1)
    G[v-1].append(u-1)

lc = LCA(N, G)
ans = 0
cnt = [0]*N

for _ in range(Q):
    a, b = map(int, input().split())
    
    if uf.is_same(a-1, b-1):
        ans += lc.dist(a-1, b-1)
    else:
        cnt[a-1] += 1
        cnt[b-1] += 1

rs = set()

for i in range(N):
    r = uf.root(i)
    rs.add(r)

par = [-1]*N
in_order = [-1]*N

for r in rs:
    total_d = dfs1(r)
    ans += dfs2(r, total_d)
    
print(ans)
0