結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー roaris
提出日時 2019-11-08 22:41:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,831 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 106,280 KB
最終ジャッジ日時 2024-09-15 01:54:06
合計ジャッジ時間 6,312 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import deque, defaultdict

class Unionfind:
    def __init__(self, n):
        self.par = [-1 for _ in range(n)]
        self.rank = [1 for _ in range(n)]
    
    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        if rx != ry:
            if self.rank[rx] >= self.rank[ry]:
                self.par[rx] += self.par[ry]
                self.par[ry] = rx
                
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] += 1
                    
            else:
                self.par[ry] += self.par[rx]
                self.par[rx] = ry
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

def bfs(s):
    depth[s] = 0
    q = deque([s])
    
    while q:
        cn = q.popleft()
        
        for nn in adj_list[cn]:
            if depth[nn] == -1:
                depth[nn] = depth[cn]+1
                parent[0][nn] = cn
                q.append(nn)

def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    
    for k in range(log_size):
        if (depth[v]-depth[u])>>k & 1:
            v = parent[k][v]
    
    if u == v:
        return u
    
    for k in range(log_size-1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]
    
    return parent[0][u]

def dist(u, v):
    l = lca(u, v)
    
    return depth[u]+depth[v]-2*depth[l]
    
N, M, Q = map(int, input().split())
uf = Unionfind(N)
adj_list = [[] for _ in range(N)]

for _ in range(M):
    ui, vi = map(int, input().split())
    uf.unite(ui-1, vi-1)
    adj_list[ui-1].append(vi-1)
    adj_list[vi-1].append(ui-1)

depth = [-1] * N
log_size = N.bit_length()
parent = [[-1] * N for _ in range(log_size)]
starts = set(uf.root(i) for i in range(N))

for s in starts:
    bfs(s)

for i in range(1, log_size):
    for j in range(N):
        if parent[i-1][j] == -1:
            parent[i][j] = -1
        else:
            parent[i][j] = parent[i-1][parent[i-1][j]]

ans = 0
cnt = defaultdict(int)

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

group = defaultdict(list)

for i in range(N):
    group[uf.root(i)].append(i)

for l in group.values():
    cost = 10**18
    
    for li in l:
        cost_cand = 0
        
        for lj in l:
            cost_cand += dist(li, lj)*cnt[lj]
    
        cost = min(cost, cost_cand)
    
    ans += cost

print(ans)
0