結果

問題 No.274 The Wall
ユーザー 東前頭十一枚目
提出日時 2019-10-03 15:32:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 2,724 bytes
コンパイル時間 1,933 ms
コンパイル使用メモリ 181,660 KB
実行使用メモリ 132,608 KB
最終ジャッジ日時 2024-06-22 02:32:40
合計ジャッジ時間 4,176 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct StronglyConnectedComponent {
	const int V;
	vector<vector<int>> G, revG;
	vector<int> id;
	StronglyConnectedComponent(const int V) :
		V(V),
		G(vector<vector<int>>(V, vector<int>())),
		revG(vector<vector<int>>(V, vector<int>())),
		id(vector<int>(V))
		{}
	void addEdge(int from, int to) {
		G[from].push_back(to);
		revG[to].push_back(from);
	}
	void build() {
		vector<bool> used(V, false);
		stack<int> st;
		for(int from = 0; from < V; ++from) {
			if(not used[from]) {
				dfs(from, used, st);
			}
		}
		int num = 0;
		while(st.size()) {
			int from = st.top();
			st.pop();
			if(used[from]) {
				revdfs(from, num, used);
				++num;
			}
		}
	}
	void dfs(int from, vector<bool> &used, stack<int> &st) {
		used[from] = true;
		for(int to : G[from]) {
			if(not used[to]) {
				dfs(to, used, st);
			}
		}
		st.push(from);
	}
	void revdfs(int from, int num, vector<bool> &used) {
		used[from] = false;
		id[from] = num;
		for(int to : revG[from]) {
			if(used[to]) {
				revdfs(to, num, used);
			}
		}
	}
	int get(int x) {
		return id[x];
	}
};

struct TwoSatisfiability {
	const int V;
	vector<vector<int>> G;
	vector<bool> pos;
	StronglyConnectedComponent scc;
	TwoSatisfiability(const int V) :
		V(V),
		G(vector<vector<int>>(2 * V, vector<int>())),
		pos(vector<bool>(2 * V)),
		scc(StronglyConnectedComponent(2 * V))
		{}
	// a or b
	void addEdge(int a, bool apos, int b, bool bpos) {
		if(not apos) a += V;
		if(not bpos) b += V;
		scc.addEdge((a + V) % (2 * V), b); // not a -> b
		scc.addEdge((b + V) % (2 * V), a); // not b -> a
	}
	bool solve() {
		scc.build();
		for(int i = 0; i < V; ++i) {
			if(scc.get(i) == scc.get(i + V)) {
				return false;
			}
			pos[i] = (scc.get(i) > scc.get(i + V));
		}
		return true;
	}
	bool get(int x) {
		return pos[x];
	}
};

int main() {
	int n, m; cin >> n >> m;
	TwoSatisfiability sat(n);
	int l[n], r[n];
	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) {
			for(int mask = 0; mask < (1 << 2); ++mask) {
				bool ipos = (mask & 1);
				bool jpos = ((mask >> 1) & 1);
				int li = l[i], ri = r[i];
				if(not ipos) {
					li = (m - 1) - li;
					ri = (m - 1) - ri;
					swap(li, ri);
				}
				int lj = l[j], rj = r[j];
				if(not jpos) {
					lj = (m - 1) - lj;
					rj = (m - 1) - rj;
					swap(lj, rj);
				}
				// 衝突するとき
				// not (A and B)
				// => (not A) or (not B)
				if(li <= lj) {
					if(lj <= ri) {
						sat.addEdge(i, not ipos, j, not jpos);
					}
				} else {
					if(li <= rj) {
						sat.addEdge(i, not ipos, j, not jpos);
					}
				}
			}
		}
	}
	cout << (sat.solve() ? "YES" : "NO") << '\n';
	return 0;
}
0