結果

問題 No.274 The Wall
ユーザー miyo2580miyo2580
提出日時 2022-08-08 19:57:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 4,965 bytes
コンパイル時間 2,657 ms
コンパイル使用メモリ 221,284 KB
実行使用メモリ 191,756 KB
最終ジャッジ日時 2023-10-19 08:34:40
合計ジャッジ時間 4,682 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 139 ms
69,508 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 3 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 419 ms
191,756 KB
testcase_12 AC 9 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 5 ms
4,348 KB
testcase_15 AC 10 ms
4,348 KB
testcase_16 AC 89 ms
41,128 KB
testcase_17 AC 86 ms
40,660 KB
testcase_18 AC 91 ms
43,632 KB
testcase_19 AC 17 ms
4,348 KB
testcase_20 AC 19 ms
4,348 KB
testcase_21 AC 20 ms
4,348 KB
testcase_22 AC 21 ms
4,348 KB
testcase_23 AC 21 ms
4,348 KB
testcase_24 AC 21 ms
4,348 KB
testcase_25 AC 21 ms
4,348 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; 

//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,m;
    cin>>n>>m;
    auto f=[&](ll a,ll b,ll c,ll d){
       if(b<c||d<a)return 0;
       else return 1;
    };
    vec l(n),r(n);
    rep(i,n)cin>>l[i]>>r[i];
    two_sat st(n);
    rep(i,n-1){
      repd(j,i+1,n){
        if(f(l[i],r[i],l[j],r[j])){
           st.add_clause(i,j);
        }
        if(f(l[i],r[i],m-1-r[j],m-1-l[j])){
          st.add_clause(i,~j);
        }
        if(f(m-1-r[i],m-1-l[i],l[j],r[j])){
          st.add_clause(~i,j);
        }
        if(f(m-1-r[i],m-1-l[i],m-1-r[j],m-1-l[j])){
          st.add_clause(~i,~j);
        }
      }
    }
    if(st.satisfiable())cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}
0