結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0