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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	outline
提出日時	2020-12-23 18:13:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	106 ms / 2,000 ms
コード長	3,360 bytes
コンパイル時間	1,456 ms
コンパイル使用メモリ	149,084 KB
実行使用メモリ	22,272 KB
最終ジャッジ日時	2024-09-21 16:28:23
合計ジャッジ時間	12,343 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,948 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	1 ms 6,944 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	1 ms 6,944 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	1 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,944 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	1 ms 6,940 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	3 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	2 ms 6,940 KB
testcase_50	AC	2 ms 6,944 KB
testcase_51	AC	2 ms 6,944 KB
testcase_52	AC	2 ms 6,944 KB
testcase_53	AC	2 ms 6,944 KB
testcase_54	AC	3 ms 6,940 KB
testcase_55	AC	2 ms 6,940 KB
testcase_56	AC	1 ms 6,944 KB
testcase_57	AC	2 ms 6,940 KB
testcase_58	AC	2 ms 6,940 KB
testcase_59	AC	2 ms 6,944 KB
testcase_60	AC	2 ms 6,940 KB
testcase_61	AC	2 ms 6,940 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	9 ms 6,940 KB
testcase_64	AC	3 ms 6,940 KB
testcase_65	AC	7 ms 6,948 KB
testcase_66	AC	5 ms 6,944 KB
testcase_67	AC	3 ms 6,944 KB
testcase_68	AC	6 ms 6,944 KB
testcase_69	AC	8 ms 6,944 KB
testcase_70	AC	4 ms 6,940 KB
testcase_71	AC	3 ms 6,940 KB
testcase_72	AC	7 ms 6,944 KB
testcase_73	AC	4 ms 6,940 KB
testcase_74	AC	7 ms 6,944 KB
testcase_75	AC	6 ms 6,940 KB
testcase_76	AC	3 ms 6,944 KB
testcase_77	AC	4 ms 6,944 KB
testcase_78	AC	9 ms 6,940 KB
testcase_79	AC	9 ms 6,940 KB
testcase_80	AC	7 ms 6,944 KB
testcase_81	AC	9 ms 6,940 KB
testcase_82	AC	8 ms 6,940 KB
testcase_83	AC	100 ms 15,628 KB
testcase_84	AC	97 ms 15,416 KB
testcase_85	AC	55 ms 10,748 KB
testcase_86	AC	76 ms 13,748 KB
testcase_87	AC	89 ms 14,552 KB
testcase_88	AC	14 ms 6,940 KB
testcase_89	AC	106 ms 15,436 KB
testcase_90	AC	61 ms 11,104 KB
testcase_91	AC	45 ms 9,480 KB
testcase_92	AC	25 ms 6,940 KB
testcase_93	AC	74 ms 13,184 KB
testcase_94	AC	67 ms 12,280 KB
testcase_95	AC	69 ms 12,260 KB
testcase_96	AC	94 ms 14,836 KB
testcase_97	AC	39 ms 8,552 KB
testcase_98	AC	93 ms 15,040 KB
testcase_99	AC	53 ms 10,520 KB
testcase_100	AC	99 ms 15,768 KB
testcase_101	AC	21 ms 6,940 KB
testcase_102	AC	11 ms 6,944 KB
testcase_103	AC	24 ms 6,944 KB
testcase_104	AC	32 ms 7,644 KB
testcase_105	AC	76 ms 13,192 KB
testcase_106	AC	44 ms 9,168 KB
testcase_107	AC	98 ms 15,440 KB
testcase_108	AC	97 ms 15,216 KB
testcase_109	AC	74 ms 13,000 KB
testcase_110	AC	69 ms 12,212 KB
testcase_111	AC	76 ms 12,572 KB
testcase_112	AC	32 ms 7,552 KB
testcase_113	AC	65 ms 11,808 KB
testcase_114	AC	42 ms 9,008 KB
testcase_115	AC	14 ms 6,940 KB
testcase_116	AC	46 ms 9,828 KB
testcase_117	AC	30 ms 7,660 KB
testcase_118	AC	94 ms 14,784 KB
testcase_119	AC	53 ms 10,268 KB
testcase_120	AC	89 ms 14,312 KB
testcase_121	AC	25 ms 6,940 KB
testcase_122	AC	46 ms 9,556 KB
testcase_123	AC	2 ms 6,940 KB
testcase_124	AC	62 ms 22,272 KB
testcase_125	AC	58 ms 22,176 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
// constexpr int mod = 1000000007;
constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template<typename G>
struct LowLink{
    const G& g;
    vector<int> visited, order, low;
    vector<int> articulation;           // 関節点
    vector<pair<int, int>> bridge;      // 橋 (order[from] < low[to])
    int LinkSize = 0;       // 連結成分の個数

    LowLink(const G &g) : g(g) {}

    int dfs(int from, int k, int par = -1){
        visited[from] = true;
        order[from] = k++;
        low[from] = order[from];
        bool is_articulation = false;
        int cnt = 0;
        for(auto &to : g[from]){
            if(!visited[to]){
                ++cnt;
                k = dfs(to, k, from);
                low[from] = min(low[from], low[to]);
                // 頂点 from がDFS木の根以外であるときの関節点となる条件
                is_articulation |= ~par && low[to] >= order[from];
                // (from, to) が条件を満たせば、橋に追加
                if(order[from] < low[to]) bridge.emplace_back(minmax(from, (int)to));
            }
            else if(to != par){
                low[from] = min(low[from], order[to]);
            }
        }
        // 頂点 from がDFS木の根であるときの関節点となる条件
        is_articulation |= par == -1 && cnt > 1;
        if(is_articulation) articulation.push_back(from);
        return k;
    }

    virtual void build(){
        visited.assign(g.size(), 0);
        order.assign(g.size(), 0);
        low.assign(g.size(), 0);
        int k = 0;
        for(int i = 0; i < g.size(); ++i){
            if(!visited[i]){
                k = dfs(i, k);
                ++LinkSize;
            }
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> a(N), b(N);
    vector<vector<int>> graph(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i] >> b[i];
        --a[i], --b[i];
        graph[a[i]].emplace_back(b[i]);
        graph[b[i]].emplace_back(a[i]);
    }

    LowLink<vector<vector<int>>> g(graph);
    g.build();
    set<P> bridge;
    for(auto [u, v] : g.bridge){
        bridge.emplace(minmax(u, v));
    }

    vector<int> ans;
    for(int i = 0; i < N; ++i){
        if(bridge.find(minmax(a[i], b[i])) != bridge.end()) continue;
        ans.emplace_back(i + 1);
    }

    int n = ans.size();
    cout << n << '\n';
    for(int i = 0; i < n; ++i){
        cout << ans[i];
        cout << ((i == n - 1) ? '\n' : ' ');
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード