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

提出ソース

結果

問題	No.1640 簡単な色塗り
ユーザー	ei1333333
提出日時	2021-08-06 23:21:29
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	199 ms / 2,000 ms
コード長	8,476 bytes
コンパイル時間	3,579 ms
コンパイル使用メモリ	214,544 KB
実行使用メモリ	19,720 KB
最終ジャッジ日時	2023-09-12 03:19:39
合計ジャッジ時間	13,626 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	56 ms 16,952 KB
testcase_05	AC	55 ms 16,952 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,384 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	55 ms 11,440 KB
testcase_11	AC	43 ms 9,988 KB
testcase_12	AC	37 ms 9,184 KB
testcase_13	AC	92 ms 15,812 KB
testcase_14	AC	96 ms 15,692 KB
testcase_15	AC	27 ms 7,692 KB
testcase_16	AC	32 ms 8,604 KB
testcase_17	AC	75 ms 13,616 KB
testcase_18	AC	6 ms 4,384 KB
testcase_19	AC	35 ms 9,220 KB
testcase_20	AC	51 ms 11,132 KB
testcase_21	AC	39 ms 9,672 KB
testcase_22	AC	5 ms 4,380 KB
testcase_23	AC	54 ms 11,576 KB
testcase_24	AC	14 ms 5,808 KB
testcase_25	AC	39 ms 9,288 KB
testcase_26	AC	64 ms 12,952 KB
testcase_27	AC	24 ms 7,284 KB
testcase_28	AC	85 ms 15,036 KB
testcase_29	AC	62 ms 12,764 KB
testcase_30	AC	11 ms 5,420 KB
testcase_31	AC	97 ms 19,720 KB
testcase_32	AC	82 ms 17,048 KB
testcase_33	AC	51 ms 12,724 KB
testcase_34	AC	74 ms 15,352 KB
testcase_35	AC	42 ms 11,744 KB
testcase_36	AC	11 ms 5,684 KB
testcase_37	AC	17 ms 6,784 KB
testcase_38	AC	81 ms 16,888 KB
testcase_39	AC	27 ms 9,816 KB
testcase_40	AC	27 ms 8,992 KB
testcase_41	AC	64 ms 15,012 KB
testcase_42	AC	30 ms 9,984 KB
testcase_43	AC	37 ms 11,020 KB
testcase_44	AC	37 ms 10,808 KB
testcase_45	AC	27 ms 9,324 KB
testcase_46	AC	10 ms 5,684 KB
testcase_47	AC	8 ms 5,296 KB
testcase_48	AC	112 ms 18,812 KB
testcase_49	AC	5 ms 4,384 KB
testcase_50	AC	1 ms 4,384 KB
testcase_51	AC	1 ms 4,380 KB
testcase_52	AC	114 ms 19,332 KB
testcase_53	AC	199 ms 18,020 KB
07_evil_01.txt	AC	277 ms 31,124 KB
07_evil_02.txt	AC	421 ms 46,248 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
// const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

/**
 * @brief Bipartite-Flow(二部グラフのフロー)
 * @docs docs/bipartite-flow.md
 */
struct BipartiteFlow {
  size_t n, m, time_stamp;
  vector< vector< int > > g, rg;
  vector< int > match_l, match_r, dist, used, alive;
  bool matched;

public:
  explicit BipartiteFlow(size_t n, size_t m) :
      n(n), m(m), g(n), rg(m), match_l(n, -1), match_r(m, -1), used(n), alive(n, 1), time_stamp(0), matched(false) {}

  void add_edge(int u, int v) {
    g[u].push_back(v);
    rg[v].emplace_back(u);
  }

  vector< pair< int, int > > max_matching() {
    matched = true;
    for(;;) {
      build_augment_path();
      ++time_stamp;
      int flow = 0;
      for(int i = 0; i < n; i++) {
        if(match_l[i] == -1) flow += find_min_dist_augment_path(i);
      }
      if(flow == 0) break;
    }
    vector< pair< int, int > > ret;
    for(int i = 0; i < n; i++) {
      if(match_l[i] >= 0) ret.emplace_back(i, match_l[i]);
    }
    return ret;
  }

  /* http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0334 */
  vector< pair< int, int > > lex_max_matching() {
    if(!matched) max_matching();
    for(auto &vs : g) sort(begin(vs), end(vs));
    vector< pair< int, int > > es;
    for(int i = 0; i < n; i++) {
      if(match_l[i] == -1 || alive[i] == 0) {
        continue;
      }
      match_r[match_l[i]] = -1;
      match_l[i] = -1;
      ++time_stamp;
      find_augment_path(i);
      alive[i] = 0;
      es.emplace_back(i, match_l[i]);
    }
    return es;
  }

  vector< int > min_vertex_cover() {
    auto visited = find_residual_path();
    vector< int > ret;
    for(int i = 0; i < n + m; i++) {
      if(visited[i] ^ (i < n)) {
        ret.emplace_back(i);
      }
    }
    return ret;
  }

  /* https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11 */
  vector< int > lex_min_vertex_cover(const vector< int > &ord) {
    assert(ord.size() == n + m);
    auto res = build_risidual_graph();
    vector< vector< int > > r_res(n + m + 2);
    for(int i = 0; i < n + m + 2; i++) {
      for(auto &j : res[i]) r_res[j].emplace_back(i);
    }
    queue< int > que;
    vector< int > visited(n + m + 2, -1);
    auto expand_left = [&](int t) {
      if(visited[t] != -1) return;
      que.emplace(t);
      visited[t] = 1;
      while(!que.empty()) {
        int idx = que.front();
        que.pop();
        for(auto &to : r_res[idx]) {
          if(visited[to] != -1) continue;
          visited[to] = 1;
          que.emplace(to);
        }
      }
    };
    auto expand_right = [&](int t) {
      if(visited[t] != -1) return;
      que.emplace(t);
      visited[t] = 0;
      while(!que.empty()) {
        int idx = que.front();
        que.pop();
        for(auto &to : res[idx]) {
          if(visited[to] != -1) continue;
          visited[to] = 0;
          que.emplace(to);
        }
      }
    };
    expand_right(n + m);
    expand_left(n + m + 1);
    vector< int > ret;
    for(auto &t : ord) {
      if(t < n) {
        expand_left(t);
        if(visited[t] & 1) ret.emplace_back(t);
      } else {
        expand_right(t);
        if(~visited[t] & 1) ret.emplace_back(t);
      }
    }
    return ret;
  }


  vector< int > max_independent_set() {
    auto visited = find_residual_path();
    vector< int > ret;
    for(int i = 0; i < n + m; i++) {
      if(visited[i] ^ (i >= n)) {
        ret.emplace_back(i);
      }
    }
    return ret;
  }

  vector< pair< int, int > > min_edge_cover() {
    auto es = max_matching();
    for(int i = 0; i < n; i++) {
      if(match_l[i] >= 0) {
        continue;
      }
      if(g[i].empty()) {
        return {};
      }
      es.emplace_back(i, g[i][0]);
    }
    for(int i = 0; i < m; i++) {
      if(match_r[i] >= 0) {
        continue;
      }
      if(rg[i].empty()) {
        return {};
      }
      es.emplace_back(rg[i][0], i);
    }
    return es;
  }

  // left: [0,n), right: [n,n+m), S: n+m, T: n+m+1
  vector< vector< int > > build_risidual_graph() {
    if(!matched) max_matching();
    const size_t S = n + m;
    const size_t T = n + m + 1;
    vector< vector< int > > ris(n + m + 2);
    for(int i = 0; i < n; i++) {
      if(match_l[i] == -1) ris[S].emplace_back(i);
      else ris[i].emplace_back(S);
    }
    for(int i = 0; i < m; i++) {
      if(match_r[i] == -1) ris[i + n].emplace_back(T);
      else ris[T].emplace_back(i + n);
    }
    for(int i = 0; i < n; i++) {
      for(auto &j : g[i]) {
        if(match_l[i] == j) ris[j + n].emplace_back(i);
        else ris[i].emplace_back(j + n);
      }
    }
    return ris;
  }

private:
  vector< int > find_residual_path() {
    auto res = build_risidual_graph();
    queue< int > que;
    vector< int > visited(n + m + 2);
    que.emplace(n + m);
    visited[n + m] = true;
    while(!que.empty()) {
      int idx = que.front();
      que.pop();
      for(auto &to : res[idx]) {
        if(visited[to]) continue;
        visited[to] = true;
        que.emplace(to);
      }
    }
    return visited;
  }

  void build_augment_path() {
    queue< int > que;
    dist.assign(g.size(), -1);
    for(int i = 0; i < n; i++) {
      if(match_l[i] == -1) {
        que.emplace(i);
        dist[i] = 0;
      }
    }
    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : g[a]) {
        int c = match_r[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool find_min_dist_augment_path(int a) {
    used[a] = time_stamp;
    for(auto &b : g[a]) {
      int c = match_r[b];
      if(c < 0 || (used[c] != time_stamp && dist[c] == dist[a] + 1 && find_min_dist_augment_path(c))) {
        match_r[b] = a;
        match_l[a] = b;
        return true;
      }
    }
    return false;
  }

  bool find_augment_path(int a) {
    used[a] = time_stamp;
    for(auto &b : g[a]) {
      int c = match_r[b];
      if(c < 0 || (alive[c] == 1 && used[c] != time_stamp && find_augment_path(c))) {
        match_r[b] = a;
        match_l[a] = b;
        return true;
      }
    }
    return false;
  }
};


int main() {
  int N;
  cin >> N;
  BipartiteFlow flow(N, N);
  for(int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    flow.add_edge(i, x);
    flow.add_edge(i, y);
  }
  auto ret = flow.max_matching();
  if(ret.size() < N) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    for(auto &p : ret) {
      cout << p.second + 1 << "\n";
    }
  }
}

yukicoder

結果

テストケース

ソースコード