結果
問題 | No.2914 正閉路検出 |
ユーザー |
![]() |
提出日時 | 2024-10-08 18:08:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,691 bytes |
コンパイル時間 | 3,765 ms |
コンパイル使用メモリ | 263,368 KB |
実行使用メモリ | 814,848 KB |
最終ジャッジ日時 | 2024-10-08 18:09:03 |
合計ジャッジ時間 | 11,852 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 13 MLE * 1 -- * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;template <typename Group, auto op, auto e, auto inv>struct DsuPotentialized {DsuPotentialized() = default;DsuPotentialized(int n) {par = vector<int>(n);sz = vector<int>(n);diff_weight = vector<Group>(n);for (int i = 0; i < n; i++) {par[i] = i;sz[i] = 1;diff_weight[i] = e();}}int find(int x) {if (par[x] == x) return x;int root = find(par[x]);diff_weight[x] = op(diff_weight[x], diff_weight[par[x]]);return par[x] = root;}bool unite(int x, int y, Group w) {w = op(w, diff_weight[x]);w = op(inv(diff_weight[y]), w);x = find(x);y = find(y);if (x == y) return false;if (sz[x] < sz[y]) {swap(x, y);w = inv(w);}par[y] = x;sz[x] += sz[y];diff_weight[y] = w;return true;}bool same(int x, int y) { return find(x) == find(y); }Group diff(int x, int y) { return op(diff_weight[y], inv(diff_weight[x])); }int size(int x) { return sz[find(x)]; }private:vector<int> par, sz;vector<Group> diff_weight;};ll op(ll a, ll b) { return a + b; }ll e() { return 0; }ll inv(ll a) { return -a; }int main() {int N, M;cin >> N >> M;DsuPotentialized<ll, op, e, inv> dsu(N);vector<vector<pair<int, int>>> G(N);for (int i = 0; i < M; i++) {int u, v, w;cin >> u >> v >> w;u--;v--;if (dsu.same(u, v)) {if (dsu.diff(u, v) != w) {vector<int> path;auto dfs = [&](auto&& dfs, int now, int pre) -> bool {if (now == v) return true;for (auto [nxt, id] : G[now]) {if (nxt == pre) continue;if (dfs(dfs, nxt, now)) {path.push_back(id);return true;}}return false;};dfs(dfs, u, -1);path.push_back(i);if (dsu.diff(u, v) > w) ranges::reverse(path);cout << ssize(path) << endl;cout << v + 1 << endl;for (int x : path) cout << x + 1 << ' ';cout << endl;return 0;}}dsu.unite(u, v, w);G[u].push_back({v, i});G[v].push_back({u, i});}cout << -1 << endl;}