結果

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

ソースコード

diff # 

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
    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, len(edges)-1))
        adj[v].append((u, len(edges)-1))

    is_bridge = [False]*M
    disc = [-1]*(N+1)
    low = [-1]*(N+1)
    time_counter = [0]

    def tarjan(u, parent_edge):
        disc[u] = low[u] = time_counter[0]
        time_counter[0] +=1
        for (v, e_idx) in adj[u]:
            if disc[v] == -1:
                tarjan(v, e_idx)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    is_bridge[e_idx] = True
            elif e_idx != parent_edge:
                low[u] = min(low[u], disc[v])

    for u in range(1, N+1):
        if disc[u] == -1:
            tarjan(u, -1)

    no_bridge_adj = [[] for _ in range(N+1)]
    for e_idx in range(M):
        u, v = edges[e_idx]
        if not is_bridge[e_idx]:
            no_bridge_adj[u].append(v)
            no_bridge_adj[v].append(u)

    two_edge_comp_id = [0]*(N+1)
    current_id = 0
    visited = [False]*(N+1)
    for u in range(1, N+1):
        if not visited[u]:
            current_id +=1
            q = deque()
            q.append(u)
            visited[u] = True
            two_edge_comp_id[u] = current_id
            while q:
                v = q.popleft()
                for neighbor in no_bridge_adj[v]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        two_edge_comp_id[neighbor] = current_id
                        q.append(neighbor)

    parent = [i for i in range(N+1)]
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root

    for u, v in edges:
        union(u, v)

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

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