#1015561 (C++17(gcc12)) No.2914 正閉路検出

• 問題: No.2914 正閉路検出
• ユーザー: Carpenters-Cat
• 提出日時: 2024-10-04 23:35:04
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: RE
• 実行時間: -
• コード長: 1,906 bytes
• コンパイル時間: 7,782 ms
• コンパイル使用メモリ: 270,788 KB
• 最終ジャッジ日時: 2025-02-24 15:41:25
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 42 RE * 13

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N, M;
    cin >> N >> M;
    using ll = long long;
    using T = tuple<int, int, ll>;
    std::vector<T> gr[200020];
    int E[200020];
    for (int i = 1; i <= M; i ++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        gr[u].emplace_back(v, i, w);
        gr[v].emplace_back(u, i, -w);
        E[i] = u ^ v;
    }
    ll D[200020];
    int pre [200020];
    fill(D, D + (N + 1), 0);
    fill(pre, pre + (N + 1), 0);
    for (int i = 1; i <= N; i ++) {
        if (pre[i]) continue;
        pre[i] = -1;
        queue<int>que;
        que.push(i);
        int beg = -1;
        int pr2 = -1;
        ll d2 = -1;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (auto& [v, p, d] : gr[u]) {
                // cout << v << " " << i << " " << d << endl;
                if (!pre[v]) {
                    pre[v] = p;
                    D[v] = D[u] + d;
                    que.push(v);
                } else if (D[v] != D[u] + d) {
                    beg = v;
                    pr2 = p;
                    d2 = D[u] + d;
                    break;
                }
            }
            if (beg != -1) break;
        }
        if (0) {
            for (int j = 1; j <= N; j ++) {
            cout << D[j] << " ";
            }
            cout << endl;
        }
        if (beg != -1) {
            ll d1 = D[beg];
            vector<int> a1, a2;
            int fl = beg;
            while (fl != i) {
                a1.push_back(pre[fl]);
                fl = fl ^ E[pre[fl]];
            }
            a2.push_back(pr2);
            fl = beg ^ E[pr2];
            while (fl != i) {
                a2.push_back(pre[fl]);
                fl = fl ^ E[pre[fl]];
            }
            if (d1 > d2) {
                swap(a1, a2);
            }
            reverse(a2.begin(), a2.end());
            for (auto& a : a2) {
                a1.push_back(a);
            }
            bool ex[200020];
            a2.clear();
            for (auto& a : a1) {
                // cout << a<< " ";
                if (ex[a]) {
                    while (ex[a]) {
                        ex[a2.back()] = false;
                        a2.pop_back();
                    }
                } else {
                    ex[a] = true;
                    a2.push_back(a);
                }
            }
            cout << a2.size() << endl;
            cout << beg << endl;
            for (int i = 0; i < a2.size(); i ++) {
                cout << a2[i] << (i + 1 < a2.size() ? " " : "");
            }
            cout << endl;
            return 0;
        }
    }
    puts("-1");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX