結果

問題 No.2914 正閉路検出
ユーザー detteiuu
提出日時 2025-03-02 07:29:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,576 bytes
コンパイル時間 608 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 173,060 KB
最終ジャッジ日時 2025-03-02 07:29:33
合計ジャッジ時間 28,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)][1]+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))
        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)
0