結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:02:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,499 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 225,828 KB
最終ジャッジ日時 2025-06-12 20:07:17
合計ジャッジ時間 26,147 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

class DSU:
    def __init__(self, size):
        self.parent = list(range(size + 1))  # 1-based indexing
        self.rank = [1] * (size + 1)
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
            self.rank[y_root] += self.rank[x_root]
        else:
            self.parent[y_root] = x_root
            self.rank[x_root] += self.rank[y_root]
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    
    edges = []
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        edges.append((u, v))
        adj[u].append(v)
        adj[v].append(u)
    
    # Tarjan's algorithm to find bridges
    disc = [-1] * (N + 1)
    low = [-1] * (N + 1)
    parent = [-1] * (N + 1)
    time = 0
    bridges = set()
    stack = []
    
    for u in range(1, N + 1):
        if disc[u] == -1:
            stack.append((u, -1, False))
            while stack:
                node, prev_node, is_processed = stack.pop()
                if is_processed:
                    for neighbor in adj[node]:
                        if neighbor == prev_node:
                            continue
                        if parent[neighbor] == node:
                            if low[neighbor] < low[node]:
                                low[node] = low[neighbor]
                            if low[neighbor] > disc[node]:
                                bridges.add((node, neighbor))
                                bridges.add((neighbor, node))
                    continue
                if disc[node] != -1:
                    continue
                disc[node] = time
                low[node] = time
                time += 1
                stack.append((node, prev_node, True))
                for neighbor in reversed(adj[node]):
                    if neighbor == prev_node:
                        continue
                    if disc[neighbor] == -1:
                        parent[neighbor] = node
                        stack.append((neighbor, node, False))
                    else:
                        if low[node] > disc[neighbor]:
                            low[node] = disc[neighbor]
    
    # Build original DSU
    original_dsu = DSU(N)
    for u, v in edges:
        original_dsu.union(u, v)
    
    # Build bridge DSU
    bridge_dsu = DSU(N)
    for u, v in edges:
        if (u, v) not in bridges:
            bridge_dsu.union(u, v)
    
    # Process queries
    output = []
    for _ in range(Q):
        x = int(input[ptr])
        ptr += 1
        y = int(input[ptr])
        ptr += 1
        if original_dsu.find(x) != original_dsu.find(y):
            output.append("No")
        else:
            if bridge_dsu.find(x) == bridge_dsu.find(y):
                output.append("No")
            else:
                output.append("Yes")
    print('\n'.join(output))

if __name__ == "__main__":
    main()
0