結果
問題 |
No.2914 正閉路検出
|
ユーザー |
![]() |
提出日時 | 2025-03-02 07:37:03 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,578 bytes |
コンパイル時間 | 485 ms |
コンパイル使用メモリ | 82,700 KB |
実行使用メモリ | 173,052 KB |
最終ジャッジ日時 | 2025-03-02 07:37:27 |
合計ジャッジ時間 | 22,895 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 WA * 24 |
ソースコード
from types import GeneratorType def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc class WeightedUnionFind: def __init__(self, n): self.par = [i for i in range(n)] self.rank = [0] * n self.weight = [0] * n def leader(self, x): if self.par[x] == x: return x else: y = self.leader(self.par[x]) self.weight[x] += self.weight[self.par[x]] self.par[x] = y return y def merge(self, x, y, w): rx = self.leader(x) ry = self.leader(y) if self.rank[rx] < self.rank[ry]: self.par[rx] = ry self.weight[rx] = w - self.weight[x] + self.weight[y] else: self.par[ry] = rx self.weight[ry] = -w - self.weight[y] + self.weight[x] if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 def same(self, x, y): return self.leader(x) == self.leader(y) def diff(self, x, y): return self.weight[x] - self.weight[y] N, M = map(int, input().split()) edge = [list(map(int, input().split())) for _ in range(M)] G = [[] for _ in range(N)] UF = WeightedUnionFind(N) s, t = -1, -1 D = dict() idx = -1 for i, (u, v, w) in enumerate(edge): u, v = u-1, v-1 MIN, MAX = min(u, v), max(u, v) if (MIN, MAX) in D: W = w if u > v: W = -W if D[(MIN, MAX)][1] != W: print(2) print(MIN+1) print(i+1, D[(MIN, MAX)][0]+1) exit() if UF.same(u, v) and UF.diff(u, v) != w: s, t = u, v idx = i break UF.merge(u, v, w) if u < v: D[(MIN, MAX)] = (i, w) else: D[(MIN, MAX)] = (i, -w) G[u].append((v, w, i)) G[v].append((u, w, i)) if s == -1: exit(print(-1)) @bootstrap def dfs(n): visited[n] = True if n == t: print(len(stack)+1) print(s+1) print(*([a+1 for a in stack]+[idx+1])) exit() for v, w, i in G[n]: if not visited[v]: stack.append(i) yield dfs(v) stack.pop() yield stack = [] visited = [False]*N dfs(s)