#173449 (C++14) No.274 The Wall

提出ソース

結果

問題	No.274 The Wall
ユーザー	oyas
提出日時	2017-05-14 09:28:30
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	392 ms / 2,000 ms
コード長	3,928 bytes
コンパイル時間	964 ms
コンパイル使用メモリ	83,760 KB
実行使用メモリ	132,224 KB
最終ジャッジ日時	2024-06-22 02:16:28
合計ジャッジ時間	2,628 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	125 ms 70,016 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	392 ms 132,224 KB
testcase_12	AC	10 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	5 ms 6,940 KB
testcase_15	AC	10 ms 6,940 KB
testcase_16	AC	93 ms 38,784 KB
testcase_17	AC	85 ms 36,992 KB
testcase_18	AC	90 ms 39,936 KB
testcase_19	AC	17 ms 6,944 KB
testcase_20	AC	19 ms 6,944 KB
testcase_21	AC	20 ms 6,940 KB
testcase_22	AC	21 ms 6,944 KB
testcase_23	AC	21 ms 6,940 KB
testcase_24	AC	21 ms 6,940 KB
testcase_25	AC	21 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 2sat.cpp
#include <vector>
#include <iostream>

#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;

typedef vector<int> vi;

// scc.cppのコピー
// 強連結成分分解 (Strongly Connected Component)
struct SCCGraph: public vector<vi> {

	vector<int> order;    // 属する強連結成分の番号(トポロジカル順序になっている)
	vector<int> vs;   // 帰りがけ順
	vector<bool> used;    // すでに調べたか

	using vector::vector;	// 継承コンストラクタ
	SCCGraph(const vector<vi> &v): vector::vector(v) {}	// コピーコンストラクタを使用可能にする

	// a -> b の辺を追加する。push_back()でも同じ
	void add_edge(int a, int b){
		(*this)[a].push_back(b);
	}

	// scc()で使う
	void dfs(int n, int k, vector<vi> &v, vector<vi> &rv){
		used[n] = true;
		order[n] = k;
		for(auto t: v[n]){
			if( !rv.empty() ) rv[t].push_back(n);	// 逆辺のグラフを作成
			if( !used[t] ) dfs(t, k, v, rv);
		}
		vs.push_back(n);
	}

	// 強連結成分分解を行う
	int scc(){
		int N = size();
		used.assign(N, false);
		order.resize(N);
		vs.clear();
		vector<vi> rG(N), tmp;   // 辺を逆にしたグラフ用
		for(int n=0; n < N; n++){
			if( !used[n] ) dfs(n, n, (*this), rG);
		}
		used.assign(N, false);
		int k = 0;		// 強連結成分の番号
		for(int i = vs.size()-1; i >= 0; i--){
			if( !used[ vs[i] ] ) dfs(vs[i], k++, rG, tmp);
		}
		return k;
	}

	// 属する強連結成分が同じかどうか判定
	bool find(int x, int y){
		return order[x] == order[y];
	}

};
// 関数としてsccを使う。戻り値は、各ノードが所属する強連結成分の番号
vector<int> scc(const vector<vi> &v){
	SCCGraph g(v);
	g.scc();
	return g.order;
}


// 2-SAT
struct TwoSAT {
	SCCGraph graph;
	int N;

	TwoSAT(int n): graph( (n+1)*2 ) {
		N = n;
	}

	// 辺( a -> b )を追加する。負の値は論理変数の否定(~a)を表す。
	void add_edge(int a, int b){
		if( a < 0 ) a = N - a;
		if( b < 0 ) b = N - b;
		graph.add_edge(a, b);
	}

	// 論理式( a V b ) を追加する。a,bは、論理変数の番号(0以外の整数)。否定は負の値で表す。
	void add_or(int a, int b){
		//if( a < 0 ) a = graph.size() - a;
		//if( b < 0 ) b = graph.size() - b;
		//int na = (a + graph.size()) % (2*graph.size());
		//int nb = (b + graph.size()) % (2*graph.size());
		add_edge(-a, b);
		add_edge(-b, a);
	}

	// 判定を行う
	bool solve(){
		graph.scc();
		bool ret = true;
		for(int i=1; i <= N; i++){
			if( graph.order[i] == graph.order[N+i] ) ret = false;
		}
		return ret;
	}

	// 変数の値を取得する。
	bool value(int a){
		if( a < 0 ) a = N - a;
		return graph.order[a] > graph.order[(N+a-1)%(2*N)+1];
	}
};


// test
// yukicoder No.274 The Wall (http://yukicoder.me/problems/no/274)
int main(){
	int N, M;
	int L[2005], R[2005];
	int rL[2005], rR[2005];
	TwoSAT sat(2005);

//	sat.add_or( 1, -2);
//	sat.add_or( 2,  3);
//	sat.add_or(-3, -1);
//	cout << sat.solve() << endl;
//	rep(i,3) cout << (sat.value(i+1) ? "true" : "false") << endl;
//
//	return 0;

	cin >> N >> M;
	rep(i,N){
		cin >> L[i] >> R[i];
		rR[i] = M - L[i] - 1;
		rL[i] = M - R[i] - 1;
		//cout << "reverse: " << rL[i] << " " << rR[i] << endl;
	}
	//auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){
	//	if( (Lj <= Li && Li <= Rj) ||
	//		(Lj <= Ri && Ri <= Rj) ||
	//		(Li <= Lj && Lj <= Ri) ||
	//		(Li <= Rj && Rj <= Ri) ){
	//		sat.add_or( -a, -b );
	//	}
	//};
	auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){
		if( !(Rj < Li || Ri < Lj) ){
			sat.add_or( -a, -b );
		}
	};
	rep(i,N) rep(j,i){
		fn(  L[i],  L[j],  R[i],  R[j],  (i+1),  (j+1) );
		fn( rL[i],  L[j], rR[i],  R[j], -(i+1),  (j+1) );
		fn(  L[i], rL[j],  R[i], rR[j],  (i+1), -(j+1) );
		fn( rL[i], rL[j], rR[i], rR[j], -(i+1), -(j+1) );
	}

	cout << (sat.solve() ? "YES" : "NO") << endl;
	//rep(i,N) cout << sat.value(i+1) << endl;

	return 0;
}