結果

問題 No.922 東北きりきざむたん
ユーザー roarisroaris
提出日時 2020-12-02 15:20:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 826 ms / 2,000 ms
コード長 4,010 bytes
コンパイル時間 528 ms
コンパイル使用メモリ 87,172 KB
実行使用メモリ 122,864 KB
最終ジャッジ日時 2023-10-11 11:27:33
合計ジャッジ時間 17,165 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
71,892 KB
testcase_01 AC 98 ms
71,784 KB
testcase_02 AC 98 ms
71,776 KB
testcase_03 AC 96 ms
71,844 KB
testcase_04 AC 108 ms
76,572 KB
testcase_05 AC 106 ms
76,672 KB
testcase_06 AC 117 ms
77,304 KB
testcase_07 AC 108 ms
76,740 KB
testcase_08 AC 114 ms
76,860 KB
testcase_09 AC 443 ms
101,132 KB
testcase_10 AC 338 ms
85,784 KB
testcase_11 AC 400 ms
96,668 KB
testcase_12 AC 272 ms
108,480 KB
testcase_13 AC 220 ms
85,980 KB
testcase_14 AC 474 ms
115,120 KB
testcase_15 AC 227 ms
112,260 KB
testcase_16 AC 690 ms
116,284 KB
testcase_17 AC 701 ms
115,624 KB
testcase_18 AC 683 ms
114,916 KB
testcase_19 AC 695 ms
116,712 KB
testcase_20 AC 687 ms
115,456 KB
testcase_21 AC 645 ms
113,292 KB
testcase_22 AC 652 ms
113,180 KB
testcase_23 AC 826 ms
122,528 KB
testcase_24 AC 801 ms
122,864 KB
testcase_25 AC 710 ms
122,192 KB
testcase_26 AC 711 ms
122,228 KB
testcase_27 AC 696 ms
121,500 KB
testcase_28 AC 251 ms
117,892 KB
testcase_29 AC 524 ms
120,380 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