#529492 (C++17) No.274 The Wall

• 問題: No.274 The Wall
• ユーザー: nok0
• 提出日時: 2020-08-14 12:04:48
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,096 ms / 2,000 ms
• コード長: 5,624 bytes
• コンパイル時間: 2,580 ms
• コンパイル使用メモリ: 207,220 KB
• 最終ジャッジ日時: 2025-01-12 22:39:51
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 22

コンパイルメッセージ

main.cpp: In function ‘void scan(char*)’:
main.cpp:54:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 | void scan(char a[]) { scanf("%s", a); }
      |                       ~~~~~^~~~~~~~~

ソースコード

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<bits/stdc++.h>
using namespace std;
#pragma region Macros
#define ll long long
#define ld long double
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
using P = pair<ll, ll>;
using Graph = VV<int>;
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);
#define VEC(type, name, size)\
    V<type> name(size);\
    IN(name)
#define VVEC(type, name, h, w)\
    VV<type> name(h, V<type>(w));\
    IN(name)
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHAR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DOUBLE(...)\
    DOUBLE __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LD(...)\
    LD __VA_ARGS__;\
    IN(__VA_ARGS__)
template <class T> void scan(T a) { cin >> a; }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T> void scan(V<T> &);
template <class T, class L> void scan(pair<T, L> &);
template <class T> void scan(V<T> &a) { for(auto &i : a) scan(i); }
template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); }
template <class T> inline void print(T x){ cout << x << '\n';}
template <class T> V<T> press(V<T> &x){ 
    V<T> res = x;
    sort(all(res));
    res.erase(unique(all(res)), res.end());
    REP(i, SZ(x)){
        x[i] = lower_bound(all(res), x[i]) - res.begin();
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
const ll INF = 1e18;
#pragma endregion
struct SCC{
    const Graph &g;
    Graph ng, rg;
    V<int> compo, order, used;
    //g:元のグラフ, ret:強連結成分分解後のグラフ
    SCC(Graph &g, Graph &ret) : g(g), ng(SZ(g)), rg(SZ(g)), compo(SZ(g), -1), used(SZ(g)){
        REP(i, SZ(g)){
            for(auto v : g[i]){
                ng[i].pb(v);
                rg[v].pb(i);
            }
        }
        build(ret);
    }
    int operator[](int k){ return compo[k];}
    void dfs(int now){
        if(used[now]) return;
        used[now] = true;
        for(auto to : ng[now]) dfs(to);
        order.eb(now);
    }
    void rdfs(int now, int count){
        if(compo[now] != -1) return;
        compo[now] = count;
        for(auto to : rg[now]) rdfs(to, count);
    }
    void build(Graph &ret){
        REP(i, SZ(ng)) dfs(i);
        reverse(rall(order));
        int group = 0;
        for(auto i : order) if(compo[i] == -1) rdfs(i, group), group++;
        ret.resize(group);
        REP(i, SZ(g)){
            for(auto &to : g[i]){
                int s = compo[i], t = compo[to];
                if(s != t) ret[s].eb(t);
            }
        }
    }
};
struct TwoSat{
    int n;
    Graph g;
    TwoSat(int n) : n(n), g(n * 2){}
    int negate(int v){return (n + v) % (n * 2);}
    void add_if(int u,int v){
        //u -> v <=> !v -> !u
        g[u].pb(v);
        g[negate(v)].pb(negate(u));
    }
    void add_and(int u, int v){
        //u and v <=> u -> v and v -> u
        add_if(u, v);
        add_if(v, u);
    }
    void add_or(int u,int v){
        //u or v <=> !u -> v
        add_if(negate(u), v);
    }
    void add_nand(int u,int v){
        //u nand v <=> u -> !v
        add_if(u, negate(v));
    }
    void set_true(int v){
        //v <=> !v ->  v
        g[negate(v)].pb(v);
    }
    void set_false(int v){
        //!v <=>  v -> !v
        g[v].pb(negate(v));
    }
    vector<int> build(){
        Graph ret;
        SCC scc(g, ret);
        vector<int> res(n);
        for(int i=0;i<n;i++){
            if(scc[i] == scc[n+i]) return {};
            res[i] = scc[i] > scc[n+i];
        }
        return res;
    }
};
int main(){
    INT(n, m);
    V<> l(n), r(n);
    REP(i, n) cin >> l[i] >> r[i];
    TwoSat TS(n);
    REP(i, n) REP(j, n){
        if(i != j){
            // iとjの区間が重なる場合
            if(!(r[i] < l[j] or r[j] < l[i])){
                TS.add_nand(i, j);
                TS.add_nand(i + n, j + n);
            }
            // iとnotjの区間が重なる場合
            if(!(r[i] < m - r[j] - 1 or m - l[j] - 1  < l[i])){
                TS.add_nand(i, j + n);
            }
        }
    }
    V<int> res = TS.build();
    YES(SZ(res));
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX