結果

問題 No.274 The Wall
ユーザー anta
提出日時 2015-08-28 22:28:40
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 240 ms
コード長 2,943 Byte
コンパイル時間 597 ms
使用メモリ 66,240 KB
最終ジャッジ日時 2019-10-20 09:01:00

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 3 ms
6,872 KB
99_system_test2.txt AC 3 ms
8,920 KB
99_system_test3.txt AC 85 ms
34,824 KB
challenge01.txt AC 3 ms
6,872 KB
sample1.txt AC 3 ms
6,876 KB
sample2.txt AC 3 ms
6,876 KB
sample3.txt AC 3 ms
6,876 KB
sample4.txt AC 3 ms
6,876 KB
system_test1.txt AC 3 ms
6,872 KB
test1.txt AC 4 ms
6,872 KB
test2.txt AC 240 ms
66,240 KB
test3.txt AC 21 ms
8,920 KB
test4.txt AC 3 ms
6,872 KB
test5.txt AC 9 ms
6,876 KB
test6.txt AC 16 ms
6,872 KB
test7.txt AC 78 ms
18,984 KB
test8.txt AC 73 ms
18,552 KB
test9.txt AC 78 ms
19,960 KB
test10.txt AC 27 ms
6,872 KB
test11.txt AC 31 ms
8,920 KB
test12.txt AC 32 ms
6,872 KB
test13.txt AC 34 ms
6,876 KB
test14.txt AC 33 ms
6,876 KB
test15.txt AC 33 ms
8,916 KB
test16.txt AC 33 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


void visit(const vector<vector<int> > &g, int v,
		vector<int> &scccolor, int &colors,
		vector<int> &S, vector<char> &inS,
		vector<int> &low, vector<int> &num, int& time) {
	low[v] = num[v] = ++time;
	S.push_back(v); inS[v] = true;
	each(e, g[v]) {
		int w = *e;
		if (num[w] == 0) {
			visit(g, w, scccolor, colors, S, inS, low, num, time);
			low[v] = min(low[v], low[w]);
		} else if (inS[w])
			low[v] = min(low[v], num[w]);
	}
	if (low[v] == num[v]) {
		while (1) {
			int w = S.back(); S.pop_back(); inS[w] = false;
			scccolor[w] = colors;
			if (v == w) break;
		}
		colors ++;
	}
}
int stronglyConnectedComponents(const vector<vector<int> >& g,
		vector<int>& scccolor) {
	const int n = g.size();
	vector<int> num(n), low(n);
	vector<int> S;
	vector<char> inS(n);
	scccolor.resize(n);
	int time = 0, colors = 0;
	rep(u, n) if (num[u] == 0)
		visit(g, u, scccolor, colors, S, inS, low, num, time);
	return colors;
}

bool two_satisfiability(const vector<vi> &g) {
	int n = g.size() / 2;
	vi scccolor;
	stronglyConnectedComponents(g, scccolor);
	rep(i, n) if(scccolor[i] == scccolor[n+i]) return false;
	return true;
}

inline bool commonPoint1D(int a, int b, int c, int d) {
	return c <= b && a <= d;
}

int main() {
	int N, M;
	while(cin >> N >> M) {
		vi L(N), R(N);
		rep(i, N)
			scanf("%d%d", &L[i], &R[i]);
		vector<vi> g(N * 2);
		rep(i, N) rep(j, i) {
			int a = L[i], b = R[i], c = L[j], d = R[j];
			rep(x, 2) {
				rep(y, 2) {
					if(commonPoint1D(a, b, c, d)) {
						g[x * N + i].push_back((1-y) * N + j);
						g[y * N + j].push_back((1-x) * N + i);
					}

					a = M - 1 - a, b = M - 1 - b, swap(a, b);
				}
				c = M - 1 - c, d = M - 1 - d, swap(c, d);
			}
		}
		bool ans = two_satisfiability(g);
		puts(ans ? "YES" : "NO");
	}
	return 0;
}
0