結果
問題 | No.274 The Wall |
ユーザー | NOSS |
提出日時 | 2019-09-23 10:49:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 558 ms / 2,000 ms |
コード長 | 4,213 bytes |
コンパイル時間 | 2,458 ms |
コンパイル使用メモリ | 191,192 KB |
実行使用メモリ | 132,608 KB |
最終ジャッジ日時 | 2024-06-22 02:32:30 |
合計ジャッジ時間 | 4,579 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 202 ms
68,864 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,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 558 ms
132,608 KB |
testcase_12 | AC | 16 ms
6,944 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,944 KB |
testcase_15 | AC | 9 ms
6,944 KB |
testcase_16 | AC | 98 ms
28,544 KB |
testcase_17 | AC | 96 ms
28,416 KB |
testcase_18 | AC | 100 ms
29,440 KB |
testcase_19 | AC | 15 ms
6,940 KB |
testcase_20 | AC | 16 ms
6,940 KB |
testcase_21 | AC | 17 ms
6,944 KB |
testcase_22 | AC | 18 ms
6,944 KB |
testcase_23 | AC | 17 ms
6,944 KB |
testcase_24 | AC | 17 ms
6,940 KB |
testcase_25 | AC | 17 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;typedef pair<ll, P> P3;typedef pair<P ,P> PP;constexpr ll MOD = 998244353;constexpr int IINF = INT_MAX;constexpr ll LLINF = LLONG_MAX;constexpr int MAX_N = int(1e6) + 5;constexpr double EPS = 1e-8;constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};#define REP(i, n) for (int i = 0; i < n; i++)#define REPR(i, n) for (int i = n; i >= 0; i--)#define SORT(v) sort((v).begin(), (v).end())#define SORTR(v) sort((v).rbegin(), (v).rend())#define ALL(v) (v).begin(), (v).end()struct SCC {int N;vector<vector<int> > g, gr, g2i, t;vector<bool> visited;vector<int> i2g;stack<int> order;SCC(){}SCC(int n){init(n);}void init(int n){N = n;g.clear();g.resize(n);gr.clear();gr.resize(n);visited.resize(n);i2g.resize(n);}void add_edge(int u, int v) {g[u].emplace_back(v);gr[v].emplace_back(u);}void dfs(int x) {if (visited[x]) return;visited[x] = true;for (int i : g[x]) dfs(i);order.push(x);}void rdfs(int x, int k) {if (i2g[x] != -1) return;i2g[x] = k;for (int i : gr[x]) rdfs(i, k);}void build() {fill(visited.begin(), visited.end(), false);fill(i2g.begin(), i2g.end(), -1);for (int i = 0; i < N; i++) dfs(i);int p = 0;while (!order.empty()) {rdfs(order.top(), p++);order.pop();}g2i.clear();g2i.resize(p);for(int i=0;i<N;i++){g2i[i2g[i]].push_back(i);}t.resize(p);for(int i=0;i<N;i++){for (auto &to : g[i]) {int x = i2g[i], y = i2g[to];if (x == y) continue;t[x].push_back(y);}}for(int i=0;i<p;i++){sort(t[i].begin(), t[i].end());t[i].erase(unique(t[i].begin(), t[i].end()),t[i].end());}}};struct TwoSAT {int N;SCC scc;vector<int> ls;TwoSAT(){}TwoSAT(int n):N(n+1),scc((n+1)*2){}int neg(int a){return (-a+N*2)%(N*2);}void add_edge(int a, int b){a = (a+N*2)%(N*2);b = (b+N*2)%(N*2);scc.add_edge(a,b);}void add_if(int a, int b){// a -> b <=> !b -> !aadd_edge(a,b);add_edge(neg(b),neg(a));}void add_iff(int a, int b){// (a <=> b) <=> a -> b and b -> a}void add_or(int a, int b){// a or b <=> !a -> b and !b -> aadd_if(neg(a),b);}void add_nand(int a, int b){// a nand b <=> a -> !b and b -> !aadd_if(a, neg(b));}void set_true(int a){// a <=> !a -> aadd_edge(neg(a), a);}void set_false(int a){// !a <=> a -> !aadd_edge(a, neg(a));}bool build(){scc.build();bool ok = true;for(int i=1;i<N;i++){ok &= scc.i2g[i] != scc.i2g[neg(i)];}if(ok){for(int i=1;i<N;i++){if(scc.i2g[i] > scc.i2g[i+N]){ls.push_back(i);}else{ls.push_back(neg(i));}}}return ok;}};int main(){int n, m;cin >> n >> m;TwoSAT twosat(n);vector<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++){if(max(l[i],l[j]) <= min(r[i],r[j])){twosat.add_nand(i+1, j+1);}if(max(m-r[i]-1,l[j]) <= min(m-l[i]-1,r[j])){twosat.add_nand(-(i+1), j+1);}if(max(l[i],m-r[j]-1) <= min(r[i],m-l[j]-1)){twosat.add_nand(i+1, -(j+1));}if(max(m-r[i]-1,m-r[j]-1) <= min(m-l[i]-1,m-l[j]-1)){twosat.add_nand(-(i+1), -(j+1));}}}cout << (twosat.build() ? "YES" : "NO") << endl;return 0;}