結果

問題 No.274 The Wall
ユーザー graph11463
提出日時 2025-04-05 19:08:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,220 bytes
コンパイル時間 1,345 ms
コンパイル使用メモリ 111,372 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-04-05 19:08:11
合計ジャッジ時間 2,819 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
using ll =long long;
void solve(){
    ll N,M;cin >> N >> M;
    vector<pair<ll,ll>> kukan(N);
    vector<vector<pair<ll,ll>>> graph(N);
    for(auto &v:kukan){
        cin >> v.first >> v.second;
    }
    for(ll i=0;i<N;i++)for(ll j=i+1;j<N;j++){
        bool bo1=true,bo2=true;
        auto[a,b]=kukan[i];
        auto[c,d]=kukan[j];
        if(b<c||d<a){
            bo1=false;
        }
        d=M-1-d,c=M-1-c;
        if(b<d||c<a){
            bo2=false;
        }
        d=M-1-d,c=M-1-c;
        //cout << i <<" " << j << endl;
        //cout << "a: " << a << " b: " << b << endl;
        //cout << "c: " << c << " d: " << d << endl;
        //cout << "rvc: " << M-1-c << " rvd: " << M-1-d << endl;
        if(bo1){
            if(bo2){
                cout << "NO" << endl;
                return;
            }else{
                graph[i].push_back(make_pair(j,1LL));
                graph[j].push_back(make_pair(i,1LL));
            }
        }else{
            if(bo2){
                graph[i].push_back(make_pair(j,0LL));
                graph[j].push_back(make_pair(i,0LL));
            }
        }
        //cout << "----------------------" <<endl;
    }
    vector<ll> nibu(N,-1);
    auto dfs = [&](auto dfs,ll cur,ll cost)->bool{
        //cout << "cur: " << cur << endl;
        nibu[cur]=cost;
        for(auto[a,b]:graph[cur]){
            if(nibu[a]==-1){
                if(!dfs(dfs,a,(cost+b)%2)){
                    return false;
                }
            }else{
                if(nibu[a]!=(cost+b)%2){
                    return false;
                }
            }
        }
        return true;
    };
    //cout << "OK" << endl;
    /*
    for(auto v:graph){
        for(auto vv:v){
            cout << vv.first << ", "<<vv.second << "| ";
        }
        cout << endl;
    }
        */
    bool bo=true;
    for(ll i=0;i<N;i++){
        if(nibu[i]==-1){
            if(!dfs(dfs,i,0)){
                bo=false;
            }
        }
    }
    if(bo){
        cout << "YES" <<endl;
    }else{
        cout <<"NO" << endl;
    }
    return;
}
int main(){
    solve();
    return 0;
}
0