結果

問題 No.274 The Wall
ユーザー monolith
提出日時 2019-03-04 11:33:46
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 340 ms / 2,000 ms
コード長 2,781 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 77,168 KB
実行使用メモリ 137,280 KB
最終ジャッジ日時 2024-06-22 02:26:07
合計ジャッジ時間 2,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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

#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<long long int, long long int> P;
long long int INF = 1e18;
long long int MOD = 1e9 + 7;
#define MAX_V 110000
int V;
vector<int> G[MAX_V]; // グラフの隣接リスト表現
vector<int> rG[MAX_V];// 辺の向きを逆にしたグラフ
vector<int> vs;       // 帰りがけ順の並び
bool used[MAX_V];     // すでに調べたか
int cmp[MAX_V];       // 属する強連結成分のトポロジカル順序
// from から to への辺を張る関数
void add_edge(int from, int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        if(!used[G[v][i]]){
            dfs(G[v][i]);
        }
    }
    vs.push_back(v);
}
void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); i++){
        if(!used[rG[v][i]]){
            rdfs(rG[v][i], k);
        }
    }
}
// 強連結成分分解を行う関数、返り値は強連結成分の個数
int scc(){
    memset(used, 0, sizeof(used));
    vs.clear();
    for(int v = 0; v < V; v++){
        if(!used[v]){
            dfs(v);
        }
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for(int i = vs.size() - 1; i >= 0; i--){
        if(!used[vs[i]]){
            rdfs(vs[i], k++);
        }
    }
    return k;
}
bool wrapped(int L1, int R1, int L2, int R2){
    if((L1 <= L2 && L2 <= R1) || (L1 <= R2 && R2 <= R1)){
        return true;
    }
    if((R2 - R1) * (L2 - L1) <= 0){
        return true;
    }
    return false;
}
int main(){
    
    int N, M;
    cin >> N >> M;
    V = N * 2;
    
    int L[2100], R[2100];
    for(int i = 0; i < N; i++){
        cin >> L[i] >> R[i];
    }
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            if(wrapped(L[i], R[i], L[j], R[j])){
                add_edge(i, j + N);
                add_edge(j, i + N);
            }
            swap(L[j], R[j]);
            L[j] = M - L[j] - 1;
            R[j] = M - R[j] - 1;
            if(wrapped(L[i], R[i], L[j], R[j])){
                add_edge(i, j);
                add_edge(j + N, i + N);
            }
            swap(L[j], R[j]);
            L[j] = M - L[j] - 1;
            R[j] = M - R[j] - 1;
            swap(L[i], R[i]);
            L[i] = M - L[i] - 1;
            R[i] = M - R[i] - 1;
            if(wrapped(L[i], R[i], L[j], R[j])){
                add_edge(i + N, j + N);
                add_edge(j, i);
            }
            swap(L[j], R[j]);
            L[j] = M - L[j] - 1;
            R[j] = M - R[j] - 1;
            if(wrapped(L[i], R[i], L[j], R[j])){
                add_edge(i + N, j);
                add_edge(j + N, i);
            }
            swap(L[i], R[i]);
            L[i] = M - L[i] - 1;
            R[i] = M - R[i] - 1;
            swap(L[j], R[j]);
            L[j] = M - L[j] - 1;
            R[j] = M - R[j] - 1;
        }
    }
    scc();
    
    // 同じ強連結成分に属するか判定
    for(int i = 0; i < N; i++){
        if(cmp[i] == cmp[i + N]){
            cout << "NO" << endl;
            return 0;
        }
    }
    
    cout << "YES" << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0