結果

問題 No.274 The Wall
ユーザー furuya1223
提出日時 2017-07-31 18:23:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 764 ms / 2,000 ms
コード長 3,339 bytes
コンパイル時間 1,917 ms
コンパイル使用メモリ 188,260 KB
実行使用メモリ 386,048 KB
最終ジャッジ日時 2024-06-22 02:20:26
合計ジャッジ時間 4,054 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
struct Edge {
    int from, to;
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
class SCCD {
public:
    stack<int> post;
    vb used;
    void dfs(int pos, int par, const Graph &G) {
        used[pos] = true;
        rep(i, G[pos].size()) {
            int to = G[pos][i].to;
            if (used[to])continue;
            dfs(to, pos, G);
        }
        post.push(pos);
    }
    void dfsrev(int pos, int par, const Graph &rev, vi &group) {
        used[pos] = true;
        group.push_back(pos);
        rep(i, rev[pos].size()) {
            int to = rev[pos][i].to;
            if (used[to])continue;
            dfsrev(to, pos, rev, group);
        }
    }
    void SCC(Graph G, vvi &scc, vi &n2g) {
        int N = G.size();
        Graph rev(N);
        rep(i, N) {
            rep(j, G[i].size()) {
                Edge e = G[i][j];
                rev[e.to].push_back(Edge{ e.to,e.from });   // 書き間違い注意
            }
        }
        used = vb(N, false);
        rep(i, N) {
            if (!used[i])dfs(i, -1, G);
        }
        fill(all(used), false);
        while (!post.empty()) {
            int pos = post.top();
            post.pop();
            if (used[pos])continue;
            vi group;
            dfsrev(pos, -1, rev, group);
            scc.push_back(group);
        }
        rep(i, scc.size()) {
            rep(j, scc[i].size()) {
                n2g[scc[i][j]] = i;
            }
        }
    }
};
class SAT {
public:
    Graph G;
    int N;
    // falseなら番号+N(変数数)
    void clause(int a, int b) {
        G[(a + N) % (2 * N)].push_back(Edge{ (a + N) % (2 * N),b});
        G[(b + N) % (2 * N)].push_back(Edge{ (b + N) % (2 * N),a });
    }
    bool satisfiable() {
        vvi scc;
        vi n2g(2 * N);
        SCCD sccd;
        sccd.SCC(G, scc, n2g);
        rep(i, N) {
            if (n2g[i] == n2g[i + N])return false;
        }
        return true;
    }
    // Nは変数の数
    SAT(int n) {
        N = n;
        G = Graph(2 * N);
    }
};
int main() {
    int N, M;
    cin >> N >> M;
    vi l(N), r(N);
    rep(i, N) {
        cin >> l[i] >> r[i];
    }
    SAT sat(N);
    rep(i, N - 1) {
        repl(j, i + 1, N) {
            if (max(l[i], l[j]) <= min(r[i], r[j])) {
                // !(i and j) <=> (!i or !j)
                sat.clause(i + N, j + N);
                sat.clause(i, j);
            }
            if (max(l[i], M - 1 - r[j]) <= min(r[i], M - 1 - l[j])) {
                // !(i and !j) <=> (!i or j)
                sat.clause(i + N, j);
                sat.clause(i, j + N);
            }
        }
    }
    if (sat.satisfiable()) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0