結果

問題 No.1640 簡単な色塗り
ユーザー miyo2580miyo2580
提出日時 2024-02-13 22:52:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 5,910 bytes
コンパイル時間 2,931 ms
コンパイル使用メモリ 228,180 KB
実行使用メモリ 34,880 KB
最終ジャッジ日時 2024-09-28 18:40:02
合計ジャッジ時間 14,450 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 45 ms
16,484 KB
testcase_05 AC 60 ms
32,484 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 47 ms
13,196 KB
testcase_11 AC 36 ms
11,168 KB
testcase_12 AC 34 ms
10,524 KB
testcase_13 AC 75 ms
18,328 KB
testcase_14 AC 75 ms
18,368 KB
testcase_15 AC 23 ms
8,432 KB
testcase_16 AC 30 ms
9,420 KB
testcase_17 AC 57 ms
15,436 KB
testcase_18 AC 6 ms
6,820 KB
testcase_19 AC 33 ms
10,248 KB
testcase_20 AC 42 ms
12,672 KB
testcase_21 AC 34 ms
11,060 KB
testcase_22 AC 5 ms
6,820 KB
testcase_23 AC 47 ms
13,512 KB
testcase_24 AC 13 ms
6,820 KB
testcase_25 AC 35 ms
10,432 KB
testcase_26 AC 51 ms
14,592 KB
testcase_27 AC 22 ms
8,068 KB
testcase_28 AC 74 ms
17,848 KB
testcase_29 AC 56 ms
14,416 KB
testcase_30 AC 10 ms
6,820 KB
testcase_31 AC 75 ms
28,076 KB
testcase_32 AC 74 ms
32,568 KB
testcase_33 AC 51 ms
21,720 KB
testcase_34 AC 56 ms
20,664 KB
testcase_35 AC 42 ms
17,480 KB
testcase_36 AC 12 ms
7,936 KB
testcase_37 AC 17 ms
11,388 KB
testcase_38 AC 71 ms
25,020 KB
testcase_39 AC 28 ms
12,640 KB
testcase_40 AC 27 ms
11,044 KB
testcase_41 AC 58 ms
22,724 KB
testcase_42 AC 30 ms
11,804 KB
testcase_43 AC 31 ms
13,960 KB
testcase_44 AC 34 ms
17,732 KB
testcase_45 AC 29 ms
16,968 KB
testcase_46 AC 11 ms
7,412 KB
testcase_47 AC 8 ms
7,424 KB
testcase_48 AC 73 ms
34,880 KB
testcase_49 AC 4 ms
6,820 KB
testcase_50 AC 2 ms
6,816 KB
testcase_51 AC 1 ms
6,816 KB
testcase_52 AC 78 ms
24,548 KB
testcase_53 AC 87 ms
31,076 KB
07_evil_01.txt AC 207 ms
36,908 KB
07_evil_02.txt AC 369 ms
52,856 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factor(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};

//https://nyaannyaan.github.io/library/math/two-sat.hpp.html

namespace TwoSatImpl {
namespace internal {

template <class E>
struct csr {
  vector<int> start;
  vector<E> elist;
  csr(int n, const vector<pair<int, E>>& edges)
      : start(n + 1), elist(edges.size()) {
    for (auto e : edges) {
      start[e.first + 1]++;
    }
    for (int i = 1; i <= n; i++) {
      start[i] += start[i - 1];
    }
    auto counter = start;
    for (auto e : edges) {
      elist[counter[e.first]++] = e.second;
    }
  }
};

struct scc_graph {
 public:
  scc_graph(int n) : _n(n) {}

  int num_vertices() { return _n; }

  void add_edge(int from, int to) { edges.push_back({from, {to}}); }

  pair<int, vector<int>> scc_ids() {
    auto g = csr<edge>(_n, edges);
    int now_ord = 0, group_num = 0;
    vector<int> visited, low(_n), ord(_n, -1), ids(_n);
    visited.reserve(_n);
    auto dfs = [&](auto self, int v) -> void {
      low[v] = ord[v] = now_ord++;
      visited.push_back(v);
      for (int i = g.start[v]; i < g.start[v + 1]; i++) {
        auto to = g.elist[i].to;
        if (ord[to] == -1) {
          self(self, to);
          low[v] = min(low[v], low[to]);
        } else {
          low[v] = min(low[v], ord[to]);
        }
      }
      if (low[v] == ord[v]) {
        while (true) {
          int u = visited.back();
          visited.pop_back();
          ord[u] = _n;
          ids[u] = group_num;
          if (u == v) break;
        }
        group_num++;
      }
    };
    for (int i = 0; i < _n; i++) {
      if (ord[i] == -1) dfs(dfs, i);
    }
    for (auto& x : ids) {
      x = group_num - 1 - x;
    }
    return {group_num, ids};
  }

  vector<vector<int>> scc() {
    auto ids = scc_ids();
    int group_num = ids.first;
    vector<int> counts(group_num);
    for (auto x : ids.second) counts[x]++;
    vector<vector<int>> groups(ids.first);
    for (int i = 0; i < group_num; i++) {
      groups[i].reserve(counts[i]);
    }
    for (int i = 0; i < _n; i++) {
      groups[ids.second[i]].push_back(i);
    }
    return groups;
  }

  void add_node_size(int m) { _n += m; }
  int size() { return _n; }

 private:
  int _n;
  struct edge {
    int to;
  };
  vector<pair<int, edge>> edges;
};

}  // namespace internal

struct two_sat {
 public:
  two_sat() : _n(0), built(false), scc(0) {}
  two_sat(int n) : _n(n), built(false), scc(2 * n) {}

  int add_var() {
    scc.add_node_size(2);
    return _n++;
  }

  // (not i) は ~i で渡す
  void add_clause(int i, int j) {
    i = max(2 * i, -1 - 2 * i);
    j = max(2 * j, -1 - 2 * j);
    assert(0 <= i && i < 2 * _n);
    assert(0 <= j && j < 2 * _n);
    scc.add_edge(i, j ^ 1);
    scc.add_edge(j, i ^ 1);
  }
  void if_then(int i, int j) { add_clause(~i, j); }
  void set_val(int i) { add_clause(i, i); }

  // (not i) は ~i で渡す
  void at_most_one(const vector<int>& nodes) {
    if ((int)nodes.size() <= 1) return;
    int cur = ~nodes[0];
    for (int i = 2; i < (int)nodes.size(); i++) {
      int nxt = add_var(), n_i = ~nodes[i];
      add_clause(cur, n_i);
      add_clause(cur, nxt);
      add_clause(n_i, nxt);
      cur = ~nxt;
    }
    add_clause(cur, ~nodes[1]);
  }

  bool satisfiable() {
    _answer.resize(_n);
    built = true;
    auto id = scc.scc_ids().second;
    for (int i = 0; i < _n; i++) {
      if (id[2 * i] == id[2 * i + 1]) {
        _answer.clear();
        return false;
      }
      _answer[i] = id[2 * i] < id[2 * i + 1];
    }
    return true;
  }
  vector<bool> answer() {
    if (!built) satisfiable();
    return _answer;
  }

 private:
  int _n;
  vector<bool> _answer;
  bool built;
  internal::scc_graph scc;
};

}  // namespace TwoSatImpl

using TwoSatImpl::two_sat;

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    two_sat ts(n);
    vector<vector<int>> g(n);
    vec a(n),b(n);
    rep(i,n){
      ll x,y;
      cin>>x>>y;
      x--;y--;
      a[i]=x;
      b[i]=y;
      g[x].push_back(i);
      g[y].push_back(~i);
    }
    rep(i,n){
      ts.at_most_one(g[i]);
    }
    if(!ts.satisfiable())cout<<"No"<<endl;
    else{
      cout<<"Yes"<<endl;
      vector<bool> ans=ts.answer();
      rep(i,n){
        if(ans[i])cout<<a[i]+1<<'\n';
        else cout<<b[i]+1<<'\n';
      }
    }
    return 0;
}
0