結果

問題 No.274 The Wall
コンテスト
ユーザー RiRinbaru
提出日時 2025-03-01 14:23:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 335 ms / 2,000 ms
コード長 3,457 bytes
コンパイル時間 3,734 ms
コンパイル使用メモリ 226,360 KB
実行使用メモリ 132,096 KB
最終ジャッジ日時 2025-03-17 19:14:01
合計ジャッジ時間 5,685 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, p, n) for (ll i = p; i < (ll)(n); i++)
#define rep2(i, p, n) for (ll i = p; i >= (ll)(n); i--)
using namespace std;
using ll = long long;
using ld = long double;
const double pi = 3.141592653589793;
const long long inf = 2 * 1e9;
const long long linf = 4 * 1e18;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

// atcoder
#include <atcoder/all>
using namespace atcoder;
using mint1 = modint1000000007;
using mint2 = modint998244353;

vector<pair<ll, ll>> base = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class TwoSAT
{
public:
    const int V;
    vector<vector<int>> G, rG;
    vector<int> ps, cmp;
    void add_edge(int from, int to)
    {
        G[from].push_back(to), rG[to].push_back(from);
    }
    void dfs(int u)
    {
        cmp[u] = 0;
        for (int v : G[u])
        {
            if (cmp[v] == -1)
                dfs(v);
        }
        ps.push_back(u);
    }
    void rdfs(int u, int k)
    {
        cmp[u] = k;
        for (int v : rG[u])
        {
            if (cmp[v] == -1)
                rdfs(v, k);
        }
    }
    int scc()
    {
        for (int i = 0; i < 2 * V; ++i)
        {
            if (cmp[i] == -1)
                dfs(i);
        }
        fill(cmp.begin(), cmp.end(), -1);
        int k = 0;
        for (int i = 2 * V - 1; i >= 0; --i)
        {
            if (cmp[ps[i]] == -1)
                rdfs(ps[i], k++);
        }
        return k;
    }
    vector<int> ans;
    TwoSAT(const int literal_count)
        : V(literal_count), G(2 * V), rG(2 * V), cmp(2 * V, -1), ans(V) {}
    void add_closure(int x, int y)
    {
        add_edge((x + V) % (2 * V), y), add_edge((y + V) % (2 * V), x);
    }
    // 充足可能性判定
    // 真のものは 1,偽のものは 0 が ans に格納される(解の構成)
    bool satisfy()
    {
        scc();
        for (int i = 0; i < V; i++)
        {
            if (cmp[i] == cmp[V + i])
                return false;
            ans[i] = (cmp[i] > cmp[V + i]);
        }
        return true;
    }
};

int main()
{

    //////////////////
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //////////////////

    ll N, M;
    cin >> N >> M;
    TwoSAT ts(N);
    vector<pair<ll, ll>> li(N);
    rep(i, 0, N)
    {
        ll x, y;
        cin >> x >> y;
        li.at(i) = {x, y};
    }
    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            if (i==j) {
                continue;
            }
            ll x1 = li.at(i).first;
            ll y1 = li.at(i).second;
            ll x2 = li.at(j).first;
            ll y2 = li.at(j).second;
            bool ch1 = (x2 <= y1 && x1 <= y2);
            x2 = M - 1 - x2;
            y2 = M - 1 - y2;
            swap(x2, y2);
            bool ch2 = (x2 <= y1 && x1 <= y2);
            // cout << i << j << ch1 << ch2 << endl;
            if (ch1)
            {
                ts.add_edge(i, j + N);
                ts.add_edge(i + N, j);
            }
            if (ch2)
            {
                ts.add_edge(i, j);
                ts.add_edge(i + N, j + N);
            }
        }
    }
    if (ts.satisfy())
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }
}
0