結果

問題 No.274 The Wall
ユーザー furuya1223furuya1223
提出日時 2017-07-31 18:23:22
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 935 ms / 2,000 ms
コード長 3,339 bytes
コンパイル時間 3,236 ms
コンパイル使用メモリ 184,720 KB
実行使用メモリ 385,816 KB
最終ジャッジ日時 2023-09-04 02:27:39
合計ジャッジ時間 5,343 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 296 ms
166,232 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 935 ms
385,816 KB
testcase_12 AC 12 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 4 ms
4,376 KB
testcase_15 AC 7 ms
4,376 KB
testcase_16 AC 111 ms
66,120 KB
testcase_17 AC 110 ms
64,836 KB
testcase_18 AC 114 ms
68,564 KB
testcase_19 AC 10 ms
4,376 KB
testcase_20 AC 11 ms
4,376 KB
testcase_21 AC 11 ms
4,380 KB
testcase_22 AC 12 ms
4,380 KB
testcase_23 AC 12 ms
4,376 KB
testcase_24 AC 12 ms
4,380 KB
testcase_25 AC 12 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
struct Edge {
	int from, to;
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

class SCCD {
public:
	stack<int> post;
	vb used;

	void dfs(int pos, int par, const Graph &G) {
		used[pos] = true;
		rep(i, G[pos].size()) {
			int to = G[pos][i].to;
			if (used[to])continue;
			dfs(to, pos, G);
		}
		post.push(pos);
	}

	void dfsrev(int pos, int par, const Graph &rev, vi &group) {
		used[pos] = true;
		group.push_back(pos);
		rep(i, rev[pos].size()) {
			int to = rev[pos][i].to;
			if (used[to])continue;
			dfsrev(to, pos, rev, group);
		}
	}

	void SCC(Graph G, vvi &scc, vi &n2g) {
		int N = G.size();
		Graph rev(N);
		rep(i, N) {
			rep(j, G[i].size()) {
				Edge e = G[i][j];
				rev[e.to].push_back(Edge{ e.to,e.from });	// 書き間違い注意
			}
		}

		used = vb(N, false);
		rep(i, N) {
			if (!used[i])dfs(i, -1, G);
		}

		fill(all(used), false);
		while (!post.empty()) {
			int pos = post.top();
			post.pop();
			if (used[pos])continue;
			vi group;
			dfsrev(pos, -1, rev, group);
			scc.push_back(group);
		}

		rep(i, scc.size()) {
			rep(j, scc[i].size()) {
				n2g[scc[i][j]] = i;
			}
		}
	}
};

class SAT {
public:
	Graph G;
	int N;

	// falseなら番号+N(変数数)
	void clause(int a, int b) {
		G[(a + N) % (2 * N)].push_back(Edge{ (a + N) % (2 * N),b});
		G[(b + N) % (2 * N)].push_back(Edge{ (b + N) % (2 * N),a });
	}

	bool satisfiable() {
		vvi scc;
		vi n2g(2 * N);
		SCCD sccd;
		sccd.SCC(G, scc, n2g);
		rep(i, N) {
			if (n2g[i] == n2g[i + N])return false;
		}
		return true;
	}

	// Nは変数の数
	SAT(int n) {
		N = n;
		G = Graph(2 * N);
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	vi l(N), r(N);
	rep(i, N) {
		cin >> l[i] >> r[i];
	}
	SAT sat(N);
	rep(i, N - 1) {
		repl(j, i + 1, N) {
			if (max(l[i], l[j]) <= min(r[i], r[j])) {
				// !(i and j) <=> (!i or !j)
				sat.clause(i + N, j + N);
				sat.clause(i, j);
			}
			if (max(l[i], M - 1 - r[j]) <= min(r[i], M - 1 - l[j])) {
				// !(i and !j) <=> (!i or j)
				sat.clause(i + N, j);
				sat.clause(i, j + N);
			}
		}
	}
	if (sat.satisfiable()) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}
0