結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー lam6er
提出日時 2025-04-15 20:59:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,696 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 241,704 KB
最終ジャッジ日時 2025-04-15 21:03:24
合計ジャッジ時間 21,808 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    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

    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(input[ptr]); ptr +=1
        v = int(input[ptr]); ptr +=1
        adj[u].append(v)
        adj[v].append(u)

    # Tarjan's algorithm to find bridges iteratively
    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    time = 1
    bridges = set()
    stack = []

    for u in range(1, N + 1):
        if disc[u] == 0:
            parent = {u: -1}
            stack.append((u, False))
            while stack:
                node, processed = stack.pop()
                if processed:
                    for v in adj[node]:
                        if v == parent.get(node, -1):
                            continue
                        if disc[v] > disc[node]:  # v is a child in DFS tree
                            if low[v] > disc[node]:
                                bridges.add((node, v))
                                bridges.add((v, node))
                            low[node] = min(low[node], low[v])
                    continue
                if disc[node] != 0:
                    continue
                disc[node] = low[node] = time
                time += 1
                stack.append((node, True))
                # Process children in reverse order to maintain adjacency order
                children = []
                for v in adj[node]:
                    if v == parent.get(node, -1):
                        continue
                    if disc[v] == 0:
                        parent[v] = node
                        children.append(v)
                    else:
                        low[node] = min(low[node], disc[v])
                for v in reversed(children):
                    stack.append((v, False))

    # Build adjacency list for 2-edge-connected components (excluding bridges)
    adj_bcc = [[] for _ in range(N+1)]
    for u in range(1, N+1):
        for v in adj[u]:
            if (u, v) not in bridges:
                adj_bcc[u].append(v)

    # Compute original connected components
    original_cc = [0] * (N + 1)
    current_cc = 0
    visited = [False] * (N + 1)
    for u in range(1, N + 1):
        if not visited[u]:
            current_cc += 1
            q = deque()
            q.append(u)
            visited[u] = True
            while q:
                v = q.popleft()
                original_cc[v] = current_cc
                for w in adj[v]:
                    if not visited[w]:
                        visited[w] = True
                        q.append(w)

    # Compute 2-edge-connected components
    bcc_id = [0] * (N + 1)
    current_bcc = 0
    visited_bcc = [False] * (N + 1)
    for u in range(1, N + 1):
        if not visited_bcc[u]:
            current_bcc += 1
            q = deque()
            q.append(u)
            visited_bcc[u] = True
            while q:
                v = q.popleft()
                bcc_id[v] = current_bcc
                for w in adj_bcc[v]:
                    if not visited_bcc[w]:
                        visited_bcc[w] = True
                        q.append(w)

    # Process queries
    output = []
    for _ in range(Q):
        x = int(input[ptr]); ptr +=1
        y = int(input[ptr]); ptr +=1
        if original_cc[x] != original_cc[y]:
            output.append("No")
        elif bcc_id[x] == bcc_id[y]:
            output.append("No")
        else:
            output.append("Yes")
    print('\n'.join(output))

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