結果

問題 No.274 The Wall
ユーザー graph11463
提出日時 2025-04-05 18:52:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,850 bytes
コンパイル時間 1,333 ms
コンパイル使用メモリ 109,416 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2025-04-05 18:52:58
合計ジャッジ時間 2,783 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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<c||d<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;
        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;
    }
    //cout << "OK" << 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;
    };
    if(dfs(dfs,0,0)){
        cout << "YES" <<endl;
    }else{
        cout <<"NO" << endl;
    }
    return;
}
int main(){
    solve();
    return 0;
}
0