結果

問題 No.3107 Listening
ユーザー SnowBeenDidingSnowBeenDiding
提出日時 2024-04-01 22:55:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,610 bytes
コンパイル時間 5,903 ms
コンパイル使用メモリ 330,776 KB
実行使用メモリ 168,892 KB
最終ジャッジ日時 2024-09-30 22:42:02
合計ジャッジ時間 12,442 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 TLE -
testcase_04 AC 313 ms
25,072 KB
testcase_05 AC 572 ms
31,516 KB
testcase_06 AC 340 ms
30,904 KB
testcase_07 AC 1,547 ms
72,172 KB
testcase_08 AC 903 ms
42,948 KB
testcase_09 AC 1,136 ms
70,300 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace std;
using namespace atcoder;

typedef long long ll;

struct edge {
    int to;
    int label;
};

vector<pair<int, int>> gabow_edmonds(const vector<vector<int>>& gra) {
    // E0 - 初期化
    int N = gra.size();
    ::std::vector<::std::vector<edge>> g(N + 1);
    ::std::vector<::std::pair<int, int>> edges;
    {
        int cnt = N + 1;
        for (int i = 0; i < N; i++) {
            for (auto to : gra[i]) {
                if (i < to) {
                    g[to + 1].push_back({i + 1, cnt});
                    g[i + 1].push_back({to + 1, cnt++});
                    edges.push_back({i + 1, to + 1});
                }
            }
        }
    }
    ::std::vector<int> mate(N + 1, 0);
    ::std::vector<int> label(N + 1, -1);
    ::std::vector<int> first(N + 1, 0);
    ::std::queue<int> que;

    // firstの遅延評価
    ::std::function<int(int)> eval_first = [&](int x) {
        if (label[first[x]] < 0) return first[x];
        first[x] = eval_first(first[x]);
        return first[x];
    };

    // サブルーチンR
    ::std::function<void(int, int)> rematch = [&](int v, int w) {
        // R1
        int t = mate[v];
        mate[v] = w;
        if (mate[t] != v) return;
        // R2
        if (label[v] <= N) {
            mate[t] = label[v];
            rematch(label[v], t);
        }
        // R3
        else {
            int x = edges[label[v] - N - 1].first;
            int y = edges[label[v] - N - 1].second;
            rematch(x, y);
            rematch(y, x);
        }
    };

    ::std::function<void(int, int, int)> assignLabel = [&](int x, int y,
                                                           int num) {
        // L0
        int r = eval_first(x);
        int s = eval_first(y);
        int join = 0;
        if (r == s) return;
        // -numがフラグ
        label[r] = -num;
        label[s] = -num;
        while (true) {
            // L1
            if (s != 0) ::std::swap(r, s);
            // L2
            r = eval_first(label[mate[r]]);
            if (label[r] == -num) {
                join = r;
                break;
            }
            label[r] = -num;
        }
        // L3
        int v = first[x];
        // L4
        while (v != join) {
            que.push(v);
            label[v] = num;
            first[v] = join;
            v = first[label[mate[v]]];
        }
        // L3
        v = first[y];
        // L4
        while (v != join) {
            que.push(v);
            label[v] = num;
            first[v] = join;
            v = first[label[mate[v]]];
        }
        // L5は遅延評価しているため不要
        // L6
        return;
    };

    ::std::function<bool(int)> augment_check = [&](int u) {
        // E1 後半
        first[u] = 0;
        label[u] = 0;
        que.push(u);
        while (!que.empty()) {
            // E2
            int x = que.front();
            que.pop();
            for (auto e : g[x]) {
                int y = e.to;
                // E3
                if (mate[y] == 0 && y != u) {
                    mate[y] = x;
                    rematch(x, y);
                    return true;
                }
                // E4
                else if (label[y] >= 0) {
                    assignLabel(x, y, e.label);
                }
                // E5
                else if (label[mate[y]] < 0) {
                    label[mate[y]] = x;
                    first[mate[y]] = y;
                    que.push(mate[y]);
                }
                // E6
            }
        }
        return false;
    };

    for (int i = 1; i <= N; i++) {
        // E1
        que = ::std::queue<int>();
        if (mate[i] != 0) continue;
        if (augment_check(i)) {
            // E7
            ::std::fill(label.begin(), label.end(), -1);
        }
    }

    ::std::vector<::std::pair<int, int>> ans;
    for (int i = 1; i <= N; i++) {
        if (i < mate[i]) {
            ans.push_back({i - 1, mate[i] - 1});
        }
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    map<pair<int, int>, int> mp;
    vector<vector<int>> gra(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        gra[a].push_back(b);
        gra[b].push_back(a);
        mp[{a, b}] = i;
        mp[{b, a}] = i;
    }
    auto ans = gabow_edmonds(gra);
    cout << ans.size() << endl;
    for (auto p : ans) {
        cout << mp[{p.first, p.second}] + 1 << endl;
    }
}
0