#566294 (C++17) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	T1610
提出日時	2020-10-13 14:55:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	170 ms / 2,000 ms
コード長	9,644 bytes
コンパイル時間	3,280 ms
コンパイル使用メモリ	231,608 KB
実行使用メモリ	30,216 KB
最終ジャッジ日時	2023-09-28 00:05:30
合計ジャッジ時間	18,030 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	0 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	2 ms 4,384 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	1 ms 4,376 KB
testcase_12	AC	1 ms 4,376 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	1 ms 4,376 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	1 ms 4,380 KB
testcase_28	AC	1 ms 4,376 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	1 ms 4,380 KB
testcase_32	AC	1 ms 4,376 KB
testcase_33	AC	2 ms 4,380 KB
testcase_34	AC	1 ms 4,380 KB
testcase_35	AC	1 ms 4,380 KB
testcase_36	AC	1 ms 4,380 KB
testcase_37	AC	1 ms 4,380 KB
testcase_38	AC	2 ms 4,376 KB
testcase_39	AC	1 ms 4,376 KB
testcase_40	AC	1 ms 4,380 KB
testcase_41	AC	1 ms 4,380 KB
testcase_42	AC	2 ms 4,380 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	1 ms 4,380 KB
testcase_46	AC	2 ms 4,380 KB
testcase_47	AC	2 ms 4,380 KB
testcase_48	AC	2 ms 4,380 KB
testcase_49	AC	1 ms 4,376 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	2 ms 4,380 KB
testcase_52	AC	2 ms 4,376 KB
testcase_53	AC	2 ms 4,380 KB
testcase_54	AC	2 ms 4,376 KB
testcase_55	AC	2 ms 4,384 KB
testcase_56	AC	2 ms 4,380 KB
testcase_57	AC	2 ms 4,376 KB
testcase_58	AC	2 ms 4,380 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	2 ms 4,376 KB
testcase_61	AC	3 ms 4,376 KB
testcase_62	AC	2 ms 4,376 KB
testcase_63	AC	13 ms 4,748 KB
testcase_64	AC	4 ms 4,380 KB
testcase_65	AC	8 ms 4,380 KB
testcase_66	AC	7 ms 4,480 KB
testcase_67	AC	4 ms 4,376 KB
testcase_68	AC	8 ms 4,380 KB
testcase_69	AC	10 ms 4,384 KB
testcase_70	AC	5 ms 4,380 KB
testcase_71	AC	4 ms 4,376 KB
testcase_72	AC	9 ms 4,540 KB
testcase_73	AC	4 ms 4,376 KB
testcase_74	AC	9 ms 4,380 KB
testcase_75	AC	7 ms 4,376 KB
testcase_76	AC	3 ms 4,380 KB
testcase_77	AC	6 ms 4,376 KB
testcase_78	AC	11 ms 4,864 KB
testcase_79	AC	12 ms 4,696 KB
testcase_80	AC	10 ms 4,768 KB
testcase_81	AC	11 ms 4,684 KB
testcase_82	AC	12 ms 4,720 KB
testcase_83	AC	157 ms 18,684 KB
testcase_84	AC	152 ms 18,600 KB
testcase_85	AC	87 ms 12,256 KB
testcase_86	AC	124 ms 16,692 KB
testcase_87	AC	134 ms 17,748 KB
testcase_88	AC	18 ms 5,508 KB
testcase_89	AC	154 ms 18,628 KB
testcase_90	AC	95 ms 12,920 KB
testcase_91	AC	75 ms 10,988 KB
testcase_92	AC	47 ms 7,276 KB
testcase_93	AC	117 ms 16,100 KB
testcase_94	AC	106 ms 14,876 KB
testcase_95	AC	102 ms 14,844 KB
testcase_96	AC	153 ms 17,840 KB
testcase_97	AC	61 ms 9,960 KB
testcase_98	AC	149 ms 18,340 KB
testcase_99	AC	80 ms 12,040 KB
testcase_100	AC	154 ms 19,004 KB
testcase_101	AC	29 ms 6,892 KB
testcase_102	AC	15 ms 5,196 KB
testcase_103	AC	33 ms 7,276 KB
testcase_104	AC	48 ms 9,196 KB
testcase_105	AC	118 ms 15,956 KB
testcase_106	AC	64 ms 10,808 KB
testcase_107	AC	152 ms 18,708 KB
testcase_108	AC	152 ms 18,396 KB
testcase_109	AC	115 ms 15,976 KB
testcase_110	AC	103 ms 14,748 KB
testcase_111	AC	115 ms 15,652 KB
testcase_112	AC	44 ms 8,540 KB
testcase_113	AC	96 ms 13,504 KB
testcase_114	AC	60 ms 10,320 KB
testcase_115	AC	19 ms 5,788 KB
testcase_116	AC	70 ms 11,340 KB
testcase_117	AC	45 ms 8,932 KB
testcase_118	AC	153 ms 17,800 KB
testcase_119	AC	86 ms 11,892 KB
testcase_120	AC	139 ms 17,548 KB
testcase_121	AC	40 ms 7,840 KB
testcase_122	AC	69 ms 11,284 KB
testcase_123	AC	1 ms 4,376 KB
testcase_124	AC	165 ms 30,216 KB
testcase_125	AC	170 ms 30,124 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}


//有向、無向グラフ共通クラス(隣接リスト)
struct Graph {
    int n;
    using WEIGHT_TYPE = long long;
    const WEIGHT_TYPE INF = 1e18;
    struct Edge {
        int to;
        WEIGHT_TYPE weight;
    };
    struct Edge2 {
        int from;
        int to;
        WEIGHT_TYPE weight;
    };
    vector<vector<Edge>> es;
    Graph(int n) : n(n), es(n) {}

    // dijkstra O(E log V)
    vector<WEIGHT_TYPE> dijkstra(int s) {
        vector<WEIGHT_TYPE> d(n, INF);
        d[s] = 0;
        using P = pair<WEIGHT_TYPE, int>;
        priority_queue<P, vector<P>, greater<P>> q;
        q.push({0LL, s});
        while(!q.empty()) {
            auto p = q.top();
            q.pop();
            int cur = p.second;
            auto cost = p.first;
            if(d[cur] < p.first) continue;
            for(auto &e : es[cur]) {
                int to = e.to;
                auto dist = e.weight + cost;
                if(dist < d[to]) {
                    d[to] = dist;
                    q.push({dist, to});
                }
            }
        }
        return d;
    }
    // dijkstra O(V^2)
    vector<WEIGHT_TYPE> dijkstra2(int s) {
        vector<WEIGHT_TYPE> d(n, INF);
        d[s] = 0;
        vector<int> used(n);
        auto mat = getEdgeMat();
        while(1) {
            int cur = -1;
            rep(i, n) {
                if(used[i]) continue;
                if(cur == -1 || d[i] < d[cur]) cur = i;
            }
            if(cur == -1) break;
            used[cur] = 1;
            rep(i, n) { chmin(d[i], d[cur] + mat[cur][i]); }
        }
        return d;
    }
    // warshall_floyd O(n^3)
    vector<vector<WEIGHT_TYPE>> warshall_floyd() {
        // vector<vector<WEIGHT_TYPE>> d(n, vector<WEIGHT_TYPE>(n, INF));
        // rep(i, n) d[i][i] = 0LL;
        // rep(i, n) for (auto && e : es[i]) {
        //     int j = e.to;
        //     chmin(d[i][j], e.weight);
        // }
        auto d = getEdgeMat();
        rep(k, n) rep(i, n) rep(j, n) { chmin(d[i][j], d[i][k] + d[k][j]); }
        return d;
    }
    // 頂点sから到達できるか
    vector<bool> getVisitable(int s) {
        vector<bool> ret(n);
        queue<int> q;
        q.push(s);
        ret[s] = true;
        while(!q.empty()) {
            auto cur = q.front();
            q.pop();
            for(auto &&e : es[cur]) {
                if(!ret[e.to]) {
                    ret[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        return ret;
    }
    // 2部グラフ判定
    bool isBipartile() {
        vector<int> memo(n, -1);
        rep(i, n) {
            if(memo[i] != -1) continue;
            queue<int> q;
            q.push(i);
            memo[i] = 0;
            while(!q.empty()) {
                auto v = q.front();
                q.pop();
                for(auto &&e : es[v]) {
                    auto u = e.to;
                    if(memo[u] == -1) {
                        memo[u] = !memo[v];
                        q.push(u);
                    } else if(memo[u] == memo[v]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    vector<vector<WEIGHT_TYPE>> getEdgeMat() {
        vector<vector<WEIGHT_TYPE>> mat(n, vector<WEIGHT_TYPE>(n, INF));
        rep(i, n) mat[i][i] = 0;
        rep(i, n) {
            for(auto &&e : es[i]) chmin(mat[i][e.to], e.weight);
        }
        return mat;
    }
};

// 無向グラフ
struct GraphUD : public Graph {
    GraphUD(int n) : Graph(n) {}
    void add_edge(int from, int to, WEIGHT_TYPE weight) {
        es[from].push_back({to, weight});
        es[to].push_back({from, weight});
    }
    vector<Edge2> getEdge2() {
        vector<Edge2> ret;
        rep(i, n) for(auto &&e : es[i]) {
            if(i < e.to) ret.push_back({i, e.to, e.weight});
        }
        return ret;
    }
    // 橋の検出
    // http://nupioca.hatenadiary.jp/entry/2013/11/03/200006
    // Calculate bridges in a undirected graph.
    // Assume graph is connected and has no parallel edges or self-loops.
    vector<Edge2> getBridges() {
        int V = n;
        // res: bridges
        vector<Edge2> res;
        // assume at least the first vertex exists
        vector<int> low(V, -1); // lowest reacheable index
        vector<int> pre(V, -1); // pre-order index
        int count = 0;          // pre-order index counter

        // v: current node
        // from: parent node
        function<int(int, int)> dfs = [&](int v, int from) {
            pre[v] = count++;
            low[v] = pre[v];
            for(auto &&e : es[v]) {
                int to = e.to;
                if(pre[to] == -1) {
                    // destination has not been visited
                    // visit destination and update low[v]
                    low[v] = min(low[v], dfs(to, v));
                    if(low[to] == pre[to]) {
                        // edge is not contained in a closed path -> bridge
                        res.push_back({v, to, e.weight});
                    }
                } else {
                    if(from == to) {
                        // ignore a path to parent
                        continue;
                    }
                    low[v] = min(low[v], low[to]);
                }
            }
            return low[v];
        };

        dfs(0, -1); // start dfs from vertex 0

        return res;
    }
};

// 有向グラフ
struct GraphD : public Graph {
    GraphD(int n) : Graph(n) {}
    void add_edge(int from, int to, WEIGHT_TYPE weight) {
        es[from].push_back({to, weight});
    }
    vector<Edge2> getEdge2() {
        vector<Edge2> ret;
        rep(i, n) for(auto &&e : es[i]) { ret.push_back({i, e.to, e.weight}); }
        return ret;
    }
    GraphD getReverseGraph() {
        GraphD g(n);
        rep(i, n) for(auto &&e : es[i]) { g.add_edge(e.to, i, e.weight); }
        return g;
    }
    vector<vector<int>> scc() {
        vector<vector<int>> res;
        vector<int> cmp(n);
        vector<int> vs;
        vector<vector<int>> r_es(n);
        rep(i, n) for(auto &&e : es[i]) {
            int j = e.to;
            r_es[j].push_back(i);
        }

        vector<bool> used(n);
        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            for(auto &&e : es[v]) {
                int to = e.to;
                if(!used[to]) dfs(to);
            }
            vs.push_back(v);
        };
        function<void(int, int)> rdfs = [&](int v, int k) {
            used[v] = true;
            cmp[v] = k;
            for(auto &&to : r_es[v]) {
                if(!used[to]) rdfs(to, k);
            }
        };

        fill(all(used), 0);
        vs.clear();
        for(int v = 0; v < n; v++) {
            if(!used[v]) dfs(v);
        }
        fill(all(used), 0);
        int k = 0;
        for(int i = vs.size() - 1; i >= 0; i--) {
            if(!used[vs[i]]) rdfs(vs[i], k++);
        }
        res.clear();
        res.resize(k);
        for(int i = 0; i < n; i++) {
            res[cmp[i]].push_back(i);
        }
        return res;
    }
    // bellmanFord 負閉路があるなら, dist[s] = INF | O(VE)
    vector<WEIGHT_TYPE> bellmanFord(int s) {
        vector<WEIGHT_TYPE> dist(n, INF);
        dist[s] = 0;
        auto es = getEdge2();
        rep(i, n) {
            for(auto &&e : es) {
                if(dist[e.to] > dist[e.from] + e.weight) {
                    dist[e.to] = dist[e.from] + e.weight;
                    if(i == n - 1) {
                        dist[s] = INF;
                        return dist;
                    }
                }
            }
        }
        return dist;
    }
    // bellmanFord s->tの経路上に負閉路があるなら, dist[s] = INF | O(VE)
    vector<WEIGHT_TYPE> bellmanFord2(int s, int t) {
        vector<WEIGHT_TYPE> dist(n, INF);
        auto f1 = getVisitable(s);
        auto f2 = getReverseGraph().getVisitable(t);
        dist[s] = 0;
        auto es = getEdge2();
        rep(i, n) {
            for(auto &&e : es) {
                if(!(f1[e.from] && f2[e.to])) continue;
                if(dist[e.to] > dist[e.from] + e.weight) {
                    dist[e.to] = dist[e.from] + e.weight;
                    if(i == n - 1) {
                        dist[s] = INF;
                        return dist;
                    }
                }
            }
        }
        return dist;
    }
};


int main(){
    int n;
    cin >> n;
    GraphUD g(n);
    using T = tuple<int, int>;
    map<T, int> mp;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        if(a > b) swap(a, b);
        g.add_edge(a, b, 1);
        mp[{a, b}] = i+1;
    }
    auto b = g.getBridges();
    for(auto&& e: b) mp.erase({min(e.from, e.to), max(e.from, e.to)});
    vi ans;
    for(auto&& m: mp) ans.emplace_back(m.second);
    sort(all(ans));
    cout << ans.size() << '\n';
    rep(i, ans.size()) cout << ans[i] << (i+1 == (int)ans.size() ? '\n' : ' ');
    return 0;
}

yukicoder

結果

テストケース

ソースコード