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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	👑 emthrm
提出日時	2021-04-19 04:57:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	213 ms / 2,000 ms
コード長	4,594 bytes
コンパイル時間	2,947 ms
コンパイル使用メモリ	235,816 KB
実行使用メモリ	32,872 KB
最終ジャッジ日時	2024-07-04 04:57:41
合計ジャッジ時間	15,876 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,948 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	2 ms 6,944 KB
testcase_39	AC	2 ms 6,944 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	3 ms 6,944 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,940 KB
testcase_49	AC	2 ms 6,944 KB
testcase_50	AC	3 ms 6,940 KB
testcase_51	AC	2 ms 6,940 KB
testcase_52	AC	3 ms 6,944 KB
testcase_53	AC	3 ms 6,944 KB
testcase_54	AC	3 ms 6,940 KB
testcase_55	AC	3 ms 6,940 KB
testcase_56	AC	2 ms 6,944 KB
testcase_57	AC	2 ms 6,944 KB
testcase_58	AC	3 ms 6,944 KB
testcase_59	AC	2 ms 6,944 KB
testcase_60	AC	2 ms 6,944 KB
testcase_61	AC	2 ms 6,944 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	11 ms 6,940 KB
testcase_64	AC	4 ms 6,940 KB
testcase_65	AC	7 ms 6,940 KB
testcase_66	AC	6 ms 6,944 KB
testcase_67	AC	3 ms 6,940 KB
testcase_68	AC	7 ms 6,944 KB
testcase_69	AC	9 ms 6,940 KB
testcase_70	AC	4 ms 6,940 KB
testcase_71	AC	4 ms 6,940 KB
testcase_72	AC	8 ms 6,944 KB
testcase_73	AC	4 ms 6,940 KB
testcase_74	AC	8 ms 6,940 KB
testcase_75	AC	6 ms 6,944 KB
testcase_76	AC	3 ms 6,940 KB
testcase_77	AC	6 ms 6,940 KB
testcase_78	AC	10 ms 6,944 KB
testcase_79	AC	11 ms 6,944 KB
testcase_80	AC	9 ms 6,944 KB
testcase_81	AC	11 ms 6,944 KB
testcase_82	AC	11 ms 6,940 KB
testcase_83	AC	177 ms 22,368 KB
testcase_84	AC	150 ms 21,940 KB
testcase_85	AC	75 ms 15,032 KB
testcase_86	AC	130 ms 19,480 KB
testcase_87	AC	148 ms 20,812 KB
testcase_88	AC	16 ms 6,940 KB
testcase_89	AC	161 ms 22,364 KB
testcase_90	AC	89 ms 15,664 KB
testcase_91	AC	67 ms 13,080 KB
testcase_92	AC	30 ms 8,524 KB
testcase_93	AC	123 ms 18,636 KB
testcase_94	AC	106 ms 17,080 KB
testcase_95	AC	112 ms 16,956 KB
testcase_96	AC	157 ms 21,476 KB
testcase_97	AC	54 ms 11,644 KB
testcase_98	AC	148 ms 21,644 KB
testcase_99	AC	83 ms 14,444 KB
testcase_100	AC	165 ms 22,832 KB
testcase_101	AC	27 ms 8,016 KB
testcase_102	AC	14 ms 6,944 KB
testcase_103	AC	29 ms 8,320 KB
testcase_104	AC	41 ms 10,296 KB
testcase_105	AC	117 ms 18,704 KB
testcase_106	AC	61 ms 12,816 KB
testcase_107	AC	166 ms 22,268 KB
testcase_108	AC	159 ms 21,944 KB
testcase_109	AC	119 ms 18,420 KB
testcase_110	AC	103 ms 16,932 KB
testcase_111	AC	126 ms 18,044 KB
testcase_112	AC	42 ms 9,984 KB
testcase_113	AC	102 ms 16,620 KB
testcase_114	AC	61 ms 12,084 KB
testcase_115	AC	18 ms 6,944 KB
testcase_116	AC	70 ms 13,504 KB
testcase_117	AC	42 ms 9,984 KB
testcase_118	AC	140 ms 21,236 KB
testcase_119	AC	79 ms 14,324 KB
testcase_120	AC	148 ms 21,528 KB
testcase_121	AC	35 ms 8,960 KB
testcase_122	AC	67 ms 13,340 KB
testcase_123	AC	2 ms 6,940 KB
testcase_124	AC	209 ms 32,616 KB
testcase_125	AC	213 ms 32,872 KB

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

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <typename CostType>
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &x) const {
    return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;
  }
  inline bool operator<=(const Edge &x) const { return !(x < *this); }
  inline bool operator>(const Edge &x) const { return x < *this; }
  inline bool operator>=(const Edge &x) const { return !(*this < x); }
};

template <typename CostType>
struct UnicyclicGraph {
  std::vector<Edge<CostType>> loop;
  std::vector<bool> is_in_loop;
  std::vector<std::vector<std::vector<Edge<CostType>>>> forest;
  std::vector<int> belong, mp;
  std::vector<std::vector<int>> inv;

  UnicyclicGraph(int n) : n(n), is_in_loop(n, false), belong(n, -1), mp(n, -1), graph(n) {}

  void add_edge(int src_i, int dst_i, CostType cost_i) {
    int id = src.size();
    graph[src_i].emplace_back(id);
    graph[dst_i].emplace_back(id);
    src.emplace_back(src_i);
    dst.emplace_back(dst_i);
    cost.emplace_back(cost_i);
  }

  void build() {
    dfs(-1, 0);
    for (int i = 0; i < n; ++i) {
      if (is_in_loop[i] && graph[i].size() > 2) {
        int idx = forest.size();
        forest.emplace_back(std::vector<std::vector<Edge<CostType>>>(1));
        belong[i] = idx;
        mp[i] = 0;
        inv.emplace_back(std::vector<int>{i});
        std::queue<int> que({i});
        while (!que.empty()) {
          int ver = que.front();
          que.pop();
          for (int id : graph[ver]) {
            int to = destination(id, ver);
            if (belong[to] == -1 && !is_in_loop[to]) {
              int nx = forest[idx].size();
              forest[idx].emplace_back();
              forest[idx][mp[ver]].emplace_back(mp[ver], nx, cost[id]);
              forest[idx][nx].emplace_back(nx, mp[ver], cost[id]);
              belong[to] = idx;
              mp[to] = nx;
              inv[idx].emplace_back(to);
              que.emplace(to);
            }
          }
        }
      }
    }
  }

private:
  int n;
  std::vector<std::vector<int>> graph;
  std::vector<int> src, dst;
  std::vector<CostType> cost;

  int destination(int id, int s) const {
    return src[id] == s ? dst[id] : src[id];
  }

  bool dfs(int prev_id, int ver) {
    is_in_loop[ver] = true;
    for (int id : graph[ver]) {
      if (id != prev_id) {
        int to = destination(id, ver);
        loop.emplace_back(ver, to, cost[id]);
        if (is_in_loop[to]) {
          for (int i = static_cast<int>(loop.size()) - 2; i >= 0; --i) {
            if (loop[i].src == to) {
              for (int j = 0; j < i; ++j) is_in_loop[loop[j].src] = false;
              loop.erase(loop.begin(), loop.begin() + i);
              break;
            }
          }
          return true;
        }
        if (dfs(id, to)) return true;
        loop.pop_back();
      }
    }
    is_in_loop[ver] = false;
    return false;
  }
};

int main() {
  int n;
  std::cin >> n;
  std::map<std::pair<int, int>, int> edge;
  UnicyclicGraph<bool> namori(n);
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    if (a > b) std::swap(a, b);
    edge[{a, b}] = i;
    namori.add_edge(a, b, false);
  }
  namori.build();
  std::vector<bool> bridge(n, false);
  for (const Edge<bool> &e : namori.loop) {
    int a = e.src, b = e.dst;
    if (a > b) std::swap(a, b);
    bridge[edge[{a, b}]] = true;
  }
  std::vector<int> p;
  for (int i = 0; i < n; ++i) {
    if (bridge[i]) p.emplace_back(i);
  }
  int k = p.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) std::cout << p[i] + 1 << " \n"[i + 1 == k];
  return 0;
}

yukicoder

結果

テストケース

ソースコード