結果
問題 |
No.1023 Cyclic Tour
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:49:45 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,093 bytes |
コンパイル時間 | 519 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 55,896 KB |
最終ジャッジ日時 | 2025-04-16 16:51:26 |
合計ジャッジ時間 | 4,882 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | TLE * 1 -- * 48 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 directed_edges = [[] for _ in range(N+1)] # 1-based in_degree = [0]*(N+1) undirected_edges = [] for _ in range(M): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 c = int(input[ptr]) ptr += 1 if c == 1: undirected_edges.append((a, b)) else: directed_edges[a].append(b) in_degree[b] += 1 # Check for cycle in directed edges using Kahn's algorithm q = deque() for i in range(1, N+1): if in_degree[i] == 0: q.append(i) processed = 0 temp_in_degree = in_degree.copy() while q: u = q.popleft() processed += 1 for v in directed_edges[u]: temp_in_degree[v] -= 1 if temp_in_degree[v] == 0: q.append(v) if processed != N: print("Yes") return # Build adjacency list for directed edges adj = [[] for _ in range(N+1)] for u in range(1, N+1): for v in directed_edges[u]: adj[u].append(v) # Precompute reachability using BFS for each node # But for large N, this is not feasible. So for each undirected edge, do BFS on demand. # However, this will be O(M * (N+M)) which is not feasible for large inputs. # But given time constraints, proceed with this approach. def bfs(start, target): visited = [False]*(N+1) q = deque() q.append(start) visited[start] = True while q: u = q.popleft() if u == target: return True for v in adj[u]: if not visited[v]: visited[v] = True q.append(v) return False for a, b in undirected_edges: if bfs(a, b) or bfs(b, a): print("Yes") return print("No") if __name__ == "__main__": main()