結果

問題 No.2914 正閉路検出
ユーザー Today03Today03
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0