結果
| 問題 |
No.1326 ふたりのDominator
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:23:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,134 bytes |
| コンパイル時間 | 238 ms |
| コンパイル使用メモリ | 82,660 KB |
| 実行使用メモリ | 176,604 KB |
| 最終ジャッジ日時 | 2025-06-12 20:23:55 |
| 合計ジャッジ時間 | 6,032 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 TLE * 1 -- * 12 |
ソースコード
import sys
from sys import stdin
from collections import defaultdict, deque
sys.setrecursionlimit(1 << 25)
def main():
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr])
ptr += 1
M = int(input[ptr])
ptr += 1
edges = []
for _ in range(M):
u = int(input[ptr])
ptr += 1
v = int(input[ptr])
ptr += 1
edges.append((u, v))
Q = int(input[ptr])
ptr += 1
queries = []
for _ in range(Q):
x = int(input[ptr])
ptr += 1
y = int(input[ptr])
ptr += 1
queries.append((x, y))
class BCC:
def __init__(self, n, edges):
self.n = n
self.edges = [[] for _ in range(n+1)]
for u, v in edges:
self.edges[u].append(v)
self.edges[v].append(u)
self.visited = [False] * (n + 1)
self.ord = [0] * (n + 1)
self.low = [0] * (n + 1)
self.parent = [0] * (n + 1)
self.k = 0
self.aps = set()
self.stack = []
self.bcc = []
self.vertex_bcc = defaultdict(list)
self.edge_bcc = defaultdict(list)
self.bcc_edges = defaultdict(set)
def dfs(self, u, root=True):
self.visited[u] = True
self.ord[u] = self.low[u] = self.k
self.k += 1
child_count = 0
is_ap = False
for v in self.edges[u]:
if not self.visited[v]:
self.parent[v] = u
self.stack.append((u, v))
child_count += 1
self.dfs(v, root=False)
self.low[u] = min(self.low[u], self.low[v])
if (root and child_count >= 2) or (not root and self.low[v] >= self.ord[u]):
is_ap = True
self.aps.add(u)
comp = []
while True:
e = self.stack.pop()
comp.append(e)
if e == (u, v):
break
self.bcc.append(comp)
elif v != self.parent[u] and self.ord[v] < self.ord[u]:
self.stack.append((u, v))
self.low[u] = min(self.low[u], self.ord[v])
if is_ap and root:
self.aps.add(u)
def find_bcc(self):
for u in range(1, self.n + 1):
if not self.visited[u]:
self.dfs(u)
comp = []
while self.stack:
e = self.stack.pop()
comp.append(e)
if comp:
self.bcc.append(comp)
for i, comp in enumerate(self.bcc):
nodes = set()
for u, v in comp:
nodes.add(u)
nodes.add(v)
self.edge_bcc[(u, v)].append(i)
self.edge_bcc[(v, u)].append(i)
for u in nodes:
self.vertex_bcc[u].append(i)
return self.aps, self.bcc, self.vertex_bcc, self.edge_bcc
bcc_ins = BCC(N, edges)
aps, bcc_list, vertex_bcc, edge_bcc = bcc_ins.find_bcc()
block_tree = defaultdict(list)
bcc_type = {}
node_count = 0
bcc_to_node = {}
ap_nodes = set()
for u in aps:
ap_nodes.add(u)
bcc_nodes = []
for i in range(len(bcc_list)):
bcc_nodes.append(i)
bcc_to_node[i] = node_count
node_count += 1
ap_to_node = {}
for ap in ap_nodes:
ap_to_node[ap] = node_count
node_count += 1
for bcc_id in range(len(bcc_list)):
comp = bcc_list[bcc_id]
nodes = set()
for u, v in comp:
nodes.add(u)
nodes.add(v)
aps_in_comp = []
for node in nodes:
if node in ap_nodes:
aps_in_comp.append(node)
for ap in aps_in_comp:
block_tree[ap_to_node[ap]].append(bcc_to_node[bcc_id])
block_tree[bcc_to_node[bcc_id]].append(ap_to_node[ap])
parent = [0] * node_count
depth = [0] * node_count
visited = [False] * node_count
for start in range(node_count):
if not visited[start]:
q = deque()
q.append(start)
visited[start] = True
parent[start] = -1
while q:
u = q.popleft()
for v in block_tree[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
depth[v] = depth[u] + 1
q.append(v)
LOG = 20
lca_table = [[-1] * node_count for _ in range(LOG)]
lca_table[0] = parent
for k in range(1, LOG):
for v in range(node_count):
if lca_table[k-1][v] != -1:
lca_table[k][v] = lca_table[k-1][lca_table[k-1][v]]
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
for k in range(LOG-1, -1, -1):
if depth[u] - (1 << k) >= depth[v]:
u = lca_table[k][u]
if u == v:
return u
for k in range(LOG-1, -1, -1):
if lca_table[k][u] != -1 and lca_table[k][u] != lca_table[k][v]:
u = lca_table[k][u]
v = lca_table[k][v]
return lca_table[0][u]
def get_bcc_node(u):
bccs = vertex_bcc.get(u, [])
if not bccs:
return -1
return bcc_to_node[bccs[0]]
def get_ap_node(u):
if u in ap_to_node:
return ap_to_node[u]
return -1
def get_path(u_node, v_node):
path = set()
ancestor = lca(u_node, v_node)
while u_node != ancestor:
path.add(u_node)
u_node = parent[u_node]
path.add(ancestor)
temp = []
while v_node != ancestor:
temp.append(v_node)
v_node = parent[v_node]
for node in reversed(temp):
path.add(node)
return path
result = []
for x, y in queries:
if x == y:
result.append(0)
continue
x_bccs = vertex_bcc.get(x, [])
y_bccs = vertex_bcc.get(y, [])
if not x_bccs or not y_bccs:
result.append(0)
continue
x_bcc = x_bccs[0]
y_bcc = y_bccs[0]
if x_bcc == y_bcc:
result.append(0)
continue
x_node = bcc_to_node[x_bcc]
y_node = bcc_to_node[y_bcc]
path = get_path(x_node, y_node)
aps_on_path = []
for node in path:
if node in ap_to_node.values():
ap = [k for k, v in ap_to_node.items() if v == node][0]
aps_on_path.append(ap)
count = 0
for ap in aps_on_path:
if ap != x and ap != y:
count += 1
result.append(count)
for res in result:
print(res)
if __name__ == '__main__':
main()