結果

問題 No.274 The Wall
ユーザー moyashi_senpaimoyashi_senpai
提出日時 2017-03-25 21:13:50
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 3,881 bytes
コンパイル時間 3,169 ms
コンパイル使用メモリ 123,260 KB
実行使用メモリ 257,896 KB
最終ジャッジ日時 2023-09-04 02:19:06
合計ジャッジ時間 4,187 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 162 ms
105,368 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,384 KB
testcase_11 AC 419 ms
257,896 KB
testcase_12 AC 24 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 9 ms
4,380 KB
testcase_15 AC 20 ms
4,376 KB
testcase_16 AC 212 ms
100,592 KB
testcase_17 AC 198 ms
95,528 KB
testcase_18 AC 211 ms
103,540 KB
testcase_19 AC 36 ms
4,376 KB
testcase_20 AC 42 ms
4,380 KB
testcase_21 AC 42 ms
4,380 KB
testcase_22 AC 45 ms
4,376 KB
testcase_23 AC 45 ms
4,380 KB
testcase_24 AC 45 ms
4,380 KB
testcase_25 AC 46 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pii Dir[8] = { //移動
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};
class Graph {
public:
	int vn;
	int sumcost = 0;
	vector<vector<pii>> g;

	Graph(int n) {
		vn = n;
		g.resize(n);
	}
	virtual void con(int a, int b, int w) = 0;
	int getWeight(int f, int t) {
		auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN));
		if (itr != g[f].end())
			return itr->second;
		return INT_MIN;
	}
	int Costsum() {
		return sumcost;
	}
};

class BiDGraph : public Graph {//無向
public:
	BiDGraph(int n) : Graph(n) {}

	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		g[b].push_back({ a, w });
		sumcost++;
	}
};
class DGraph : public Graph {//有向
public:
	DGraph(int n) : Graph(n) {}
	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		sumcost++;
	}
};

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0;
	int k = 0;
	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}

bool TWO_SAT(int n, vector<pii> clause) {//否定は-, 1-indexed
	DGraph g(n * 2);
	for (auto itr : clause) {
		int a = (itr.first < 0 ? -itr.first+n : itr.first)-1, b = (itr.second < 0 ? -itr.second+ n : itr.second)-1;
		g.con(a + (a>=n?-n:n),b);
		g.con(b + (b >= n ? -n : n),a);
	}
	vector<int> scc;
	SCC(g, scc);

	REP(i, n) {
		if (scc[i] == scc[i + n]) {
			return 0;
		}
	}

	return 1;
}

signed main() {
	int n, m;
	scanf("%d %d", &n, &m);

	vector<pii> wall(n);
	REP(i,n){
		scanf("%d %d", &wall[i].first, &wall[i].second);
	}
	vector<pii> clause;

	for (int i = 0; n * 2 > i; i += 2) {
		clause.push_back({ -(i + 1), -(i + 2) });
		clause.push_back({ (i + 1), (i + 2) });
		pii ti = wall[i/2];
		REP(ci, 2) {
			for (int j = i + 2; n * 2 > j; j += 2) {
				pii tj = wall[j/2];
				REP(cj, 2) {
					if (DUPLE(ti.first, ti.second, tj.first, tj.second)) {
						clause.push_back({ -(i + ci + 1), -(j + cj + 1) });
					}
				tj = { m - wall[j/2].second - 1,m - wall[j/2].first - 1 };
				}
			}
			ti = { m - wall[i/2].second - 1,m - wall[i/2].first - 1 };
		}
	}
	printf("%s\n", TWO_SAT(n*2, clause) ? "YES" : "NO");

	return 0;
}
0