結果

問題 No.274 The Wall
ユーザー KKT89
提出日時 2024-03-07 22:23:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,151 ms / 2,000 ms
コード長 3,407 bytes
コンパイル時間 3,062 ms
コンパイル使用メモリ 225,948 KB
最終ジャッジ日時 2025-02-20 01:46:11
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
vector<int> scc(const vector<vector<int>> &g) {
int n = (int)g.size();
int cnt = 0;
vector<vector<int>> rg(n);
vector<int> order;
vector<int> res(n, -1);
vector<bool> used(n);
for (int i = 0; i < n; ++i) {
for (int j : g[i]) rg[j].push_back(i);
}
auto dfs1 = [&](auto self, int s) -> void {
used[s] = true;
for (int t : g[s]) {
if (!used[t]) self(self, t);
}
order.push_back(s);
};
auto dfs2 = [&](auto self, int s) -> void {
for (int t : rg[s]) {
if (res[t] == -1) {
res[t] = res[s];
self(self, t);
}
}
};
order.reserve(n);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs1(dfs1, i);
}
}
reverse(order.begin(), order.end());
for (int i : order) {
if (res[i] == -1) {
res[i] = cnt++;
dfs2(dfs2, i);
}
}
return res;
}
struct twosat {
int n;
vector<vector<int>> g;
twosat(int n) : n(n), g(2*n) {}
// (i = f1) || (j = f2)
void add_clause(int i, bool f1, int j, bool f2) {
g[(i << 1) ^ !f1].emplace_back((j << 1) ^ f2);
g[(j << 1) ^ !f2].emplace_back((i << 1) ^ f1);
}
// (i = f1) -> (j = f2) <=> (i = !f1) || (j = f2)
void add_if(int i, bool f1, int j, bool f2) {
add_clause(i, !f1, j, f2);
}
// i
void set_true(int i) {
add_clause(i, true, i, true);
}
// !i
void set_false(int i) {
add_clause(i, false, i, false);
}
vector<bool> solve() {
vector<int> c = scc(g);
vector<bool> res(n);
for (int i = 0; i < n; ++i) {
if (c[i << 1] == c[i << 1 | 1]) return vector<bool>();
res[i] = (c[i << 1] < c[i << 1 | 1]);
}
return res;
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n; cin >> n;
int m; cin >> m;
vector<int> l(n), r(n);
for (int i = 0; i < n; ++i) {
cin >> l[i] >> r[i];
l[i] += 1;
r[i] += 1;
}
twosat ts(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
auto check = [&](int l1, int r1, int l2, int r2) -> bool {
return max(l1, l2) > min(r1, r2);
};
if (!check(l[i], r[i], l[j], r[j])) {
ts.add_if(i, false, j, true);
}
if (!check(l[i], r[i], m+1-r[j], m+1-l[j])) {
ts.add_if(i, false, j, false);
}
if (!check(m+1-r[i], m+1-l[i], l[j], r[j])) {
ts.add_if(i, true, j, true);
}
if (!check(m+1-r[i], m+1-l[i], m+1-r[j], m+1-l[j])) {
ts.add_if(i, true, j, false);
}
}
}
if (ts.solve().size()) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0