結果

問題 No.274 The Wall
ユーザー monolithmonolith
提出日時 2019-03-04 11:33:46
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 398 ms / 2,000 ms
コード長 2,781 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 78,240 KB
実行使用メモリ 137,240 KB
最終ジャッジ日時 2023-09-04 02:37:03
合計ジャッジ時間 3,215 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,656 KB
testcase_01 AC 5 ms
8,756 KB
testcase_02 AC 4 ms
8,656 KB
testcase_03 AC 140 ms
74,152 KB
testcase_04 AC 5 ms
8,648 KB
testcase_05 AC 5 ms
8,584 KB
testcase_06 AC 5 ms
8,648 KB
testcase_07 AC 5 ms
8,696 KB
testcase_08 AC 5 ms
8,588 KB
testcase_09 AC 5 ms
8,616 KB
testcase_10 AC 5 ms
8,636 KB
testcase_11 AC 398 ms
137,240 KB
testcase_12 AC 34 ms
8,704 KB
testcase_13 AC 6 ms
8,628 KB
testcase_14 AC 11 ms
8,748 KB
testcase_15 AC 21 ms
8,784 KB
testcase_16 AC 237 ms
89,420 KB
testcase_17 AC 217 ms
85,184 KB
testcase_18 AC 221 ms
87,936 KB
testcase_19 AC 33 ms
8,836 KB
testcase_20 AC 37 ms
9,120 KB
testcase_21 AC 39 ms
8,848 KB
testcase_22 AC 41 ms
8,860 KB
testcase_23 AC 40 ms
8,948 KB
testcase_24 AC 42 ms
8,932 KB
testcase_25 AC 42 ms
8,920 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0