#686781 (C++17) No.1640 簡単な色塗り

提出ソース

結果

問題	No.1640 簡単な色塗り
ユーザー	keijak
提出日時	2021-08-06 22:31:11
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	108 ms / 2,000 ms
コード長	4,377 bytes
コンパイル時間	2,413 ms
コンパイル使用メモリ	218,152 KB
実行使用メモリ	15,944 KB
最終ジャッジ日時	2024-06-29 15:33:41
合計ジャッジ時間	12,404 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	40 ms 9,920 KB
testcase_05	AC	40 ms 9,956 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	36 ms 7,168 KB
testcase_11	AC	29 ms 6,944 KB
testcase_12	AC	26 ms 6,944 KB
testcase_13	AC	56 ms 9,168 KB
testcase_14	AC	56 ms 9,248 KB
testcase_15	AC	19 ms 6,944 KB
testcase_16	AC	22 ms 6,940 KB
testcase_17	AC	45 ms 8,192 KB
testcase_18	AC	5 ms 6,944 KB
testcase_19	AC	25 ms 6,940 KB
testcase_20	AC	35 ms 7,040 KB
testcase_21	AC	28 ms 6,944 KB
testcase_22	AC	4 ms 6,940 KB
testcase_23	AC	38 ms 7,552 KB
testcase_24	AC	11 ms 6,940 KB
testcase_25	AC	27 ms 6,940 KB
testcase_26	AC	42 ms 7,796 KB
testcase_27	AC	18 ms 6,944 KB
testcase_28	AC	53 ms 9,004 KB
testcase_29	AC	41 ms 7,680 KB
testcase_30	AC	8 ms 6,940 KB
testcase_31	AC	55 ms 15,944 KB
testcase_32	AC	47 ms 12,856 KB
testcase_33	AC	33 ms 10,112 KB
testcase_34	AC	41 ms 11,776 KB
testcase_35	AC	24 ms 7,808 KB
testcase_36	AC	9 ms 6,940 KB
testcase_37	AC	13 ms 6,944 KB
testcase_38	AC	41 ms 11,552 KB
testcase_39	AC	19 ms 7,808 KB
testcase_40	AC	17 ms 6,940 KB
testcase_41	AC	37 ms 10,752 KB
testcase_42	AC	19 ms 7,296 KB
testcase_43	AC	26 ms 8,832 KB
testcase_44	AC	26 ms 8,704 KB
testcase_45	AC	20 ms 7,808 KB
testcase_46	AC	8 ms 6,940 KB
testcase_47	AC	7 ms 6,940 KB
testcase_48	AC	59 ms 14,732 KB
testcase_49	AC	4 ms 6,944 KB
testcase_50	AC	2 ms 6,944 KB
testcase_51	AC	2 ms 6,940 KB
testcase_52	AC	63 ms 14,572 KB
testcase_53	AC	108 ms 11,752 KB
07_evil_01.txt	AC	152 ms 16,616 KB
07_evil_02.txt	AC	240 ms 23,380 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#define REP_(i, a_, b_, a, b, ...) \
  for (int i = (a), END_##i = (b); i < END_##i; ++i)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(x) std::begin(x), std::end(x)
using i64 = long long;

template<typename T, typename U>
inline bool chmax(T &a, U b) {
  return a < b and ((a = std::move(b)), true);
}
template<typename T, typename U>
inline bool chmin(T &a, U b) {
  return a > b and ((a = std::move(b)), true);
}
template<typename T>
inline int ssize(const T &a) {
  return (int) std::size(a);
}

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
  for (auto &x : a) is >> x;
  return is;
}
template<typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &a) {
  return os << "(" << a.first << ", " << a.second << ")";
}
template<typename Container>
std::ostream &print_seq(const Container &a, std::string_view sep = " ",
                        std::string_view ends = "\n",
                        std::ostream &os = std::cout) {
  auto b = std::begin(a), e = std::end(a);
  for (auto it = std::begin(a); it != e; ++it) {
    if (it != b) os << sep;
    os << *it;
  }
  return os << ends;
}
template<typename T, typename = void>
struct is_iterable : std::false_type {};
template<typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),
                                  decltype(std::end(std::declval<T>()))>>
    : std::true_type {
};

template<typename T, typename = std::enable_if_t<
    is_iterable<T>::value &&
        !std::is_same<T, std::string_view>::value &&
        !std::is_same<T, std::string>::value>>
std::ostream &operator<<(std::ostream &os, const T &a) {
  return print_seq(a, ", ", "", (os << "{")) << "}";
}

void print() { std::cout << "\n"; }
template<class T>
void print(const T &x) {
  std::cout << x << "\n";
}
template<typename Head, typename... Tail>
void print(const Head &head, Tail... tail) {
  std::cout << head << " ";
  print(tail...);
}

void read_from_cin() {}
template<typename T, typename... Ts>
void read_from_cin(T &value, Ts &...args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define INPUT(type, ...) \
  type __VA_ARGS__;      \
  read_from_cin(__VA_ARGS__)

#ifdef MY_DEBUG
#include "debug_dump.hpp"
#else
#define DUMP(...)
#endif

using namespace std;

struct HopcroftKarp {
  vector<vector<int> > graph;
  vector<int> dist, match;
  vector<bool> used, vv;

  HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}

  void add_edge(int u, int v) {
    graph[u].push_back(v);
  }

  void bfs() {
    dist.assign(graph.size(), -1);
    queue<int> que;
    for (int i = 0; i < (int) graph.size(); i++) {
      if (!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while (!que.empty()) {
      int a = que.front();
      que.pop();
      for (auto &b : graph[a]) {
        int c = match[b];
        if (c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a) {
    vv[a] = true;
    for (auto &b : graph[a]) {
      int c = match[b];
      if (c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching() {
    int ret = 0;
    while (true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for (int i = 0; i < (int) graph.size(); i++) {
        if (!used[i] && dfs(i)) ++flow;
      }
      if (flow == 0) return (ret);
      ret += flow;
    }
  }

  void output() {
    for (int i = 0; i < (int) match.size(); i++) {
      if (~match[i]) {
        cout << match[i] << "-" << i << endl;
      }
    }
  }
};

auto solve() -> optional<vector<int>> {
  INPUT(int, n);
  HopcroftKarp bm(n, n);
  REP(i, n) {
    INPUT(int, a, b);
    --a, --b;
    bm.add_edge(i, a);
    bm.add_edge(i, b);
  }
  auto matching = bm.bipartite_matching();
  DUMP(matching);
  if (matching != n) return nullopt;

  DUMP(bm.match);
  vector<int> ans(n);
  REP(i, n) {
    ans[bm.match[i]] = i + 1;
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  auto ans = solve();
  if (not ans) {
    print("No");
  } else {
    print("Yes");
    print_seq(ans.value(), "\n");
  }
}

yukicoder

結果

テストケース

ソースコード