結果

問題 No.274 The Wall
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-10-11 11:13:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 436 ms / 2,000 ms
コード長 3,429 bytes
コンパイル時間 2,228 ms
コンパイル使用メモリ 182,384 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2024-06-22 02:33:17
合計ジャッジ時間 4,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 154 ms
68,864 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 436 ms
132,480 KB
testcase_12 AC 23 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 7 ms
6,940 KB
testcase_15 AC 15 ms
6,940 KB
testcase_16 AC 145 ms
50,560 KB
testcase_17 AC 133 ms
47,872 KB
testcase_18 AC 146 ms
50,944 KB
testcase_19 AC 27 ms
6,944 KB
testcase_20 AC 29 ms
6,940 KB
testcase_21 AC 30 ms
6,940 KB
testcase_22 AC 32 ms
6,944 KB
testcase_23 AC 32 ms
6,940 KB
testcase_24 AC 31 ms
6,944 KB
testcase_25 AC 33 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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))
		{}
	inline int NOT(int A) {
		return (A + V) % (2 * V);
	}
	// A -> B <=> not B -> not A
	inline void addIF(int A, bool Apos, int B, bool Bpos) {
		if(not Apos) A = NOT(A);
		if(not Bpos) B = NOT(B);
		scc.addEdge(A, B); // A -> B
		scc.addEdge(NOT(B), NOT(A)); // not B -> not A
	}
	// A <=> (not A -> A)
	void addUNARY(int A, bool Apos) {
		addIF(A, not Apos, A, Apos); // not A -> A
	}
	// A or B <=> not A -> B
	void addOR(int A, bool Apos, int B, bool Bpos) {
		addIF(A, not Apos, B, not Bpos); // not A -> B
	}
	// not(A and B) => A -> not B
	void addNAND(int A, bool Apos, int B, bool Bpos) {
		addIF(A, Apos, B, not Bpos); // A -> not B
	}
	// A xor B <=> not(A and B) and not(not A and not B)
	void addXOR(int A, bool Apos, int B, bool Bpos) {
		addNAND(A, Apos, B, Bpos); // not(A and B)
		addNAND(A, not Apos, B, not Bpos); // not(not A and not B)
	}
	// not(A xor B) <=> A xor not B
	void addXNOR(int A, bool Apos, int B, bool Bpos) {
		addXOR(A, Apos, B, not Bpos); // A xor not B
	}
	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);
				}
				if(li <= lj) {
					if(lj <= ri) {
						sat.addNAND(i, not ipos, j, not jpos);
					}
				} else {
					if(li <= rj) {
						sat.addNAND(i, not ipos, j, not jpos);
					}
				}
			}
		}
	}
	cout << (sat.solve() ? "YES" : "NO") << '\n';
	return 0;
}
0