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

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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