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

• 問題: No.274 The Wall
• ユーザー: WA_TLE
• 提出日時: 2017-06-29 23:46:05
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 544 ms / 2,000 ms
• コード長: 4,027 bytes
• コンパイル時間: 1,588 ms
• コンパイル使用メモリ: 115,104 KB
• 最終ジャッジ日時: 2025-01-05 00:54:58
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const int big=1e9+1e8;
const llint red=0xE869120;
const llint pro=1002001;
const long double pai=3.141592653589793238462643383279;
//JOI Building 2
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
class SCC{
    /*
    使い方
    roadに辺を、rroadにその逆を突っ込んでください
    メンバ関数のdo_sccしてください
    unite_sccでまとめることができます
    */
public:
    vector<vector<int>>road;
    vector<vector<int>>rroad;
    vector<int>ban;//帰りがけ順の場所
    vector<bool>sir;//調べたらtrue
    vector<int>uni;//同じ連結成分かどうか,トポロジカル順序になっている
    int n,num,kyonum;
    SCC(void){}
    SCC(int in){n=in;road.res(n);rroad.res(n);}
    inline void add_road(int a,int b){road[a].pub(b);rroad[b].pub(a);}
    void dfs_scc(int town){
        if(sir[town]){return;}
        sir[town]=true;//cout<<"de "<<town<<endl;
        for(int i=0;i<road[town].size();i++){dfs_scc(road[town][i]);}
        ban.pub(town);
        return;
    }
    void rdfs_scc(int town){
        if(uni[town]!=0){return;}
        uni[town]=kyonum;//cout<<"rde "<<town<<endl;
        for(int i=0;i<rroad[town].size();i++){rdfs_scc(rroad[town][i]);}
        return;
    }
    void do_scc(void){
        //同じ連結成分を同じ組にしたvectorを返す
        //chain_sccにそれをかますと頂点をまとめてDAGにしてくれる
        n=road.size();
        num=1;
        sir.res(n);
        uni.res(n);
        int i,j;
        for(i=0;i<n;i++){dfs_scc(i);}
        kyonum=1;
        for(i=0;i<n;i++){if(uni[ban[n-i-1]]==0){rdfs_scc(ban[n-i-1]);kyonum++;}}
        return;
    }//kyonumの数だけ成分がある
    vector<vector<int>>Croad;
    vector<vector<int>>Crroad;
    void chain_scc(void){
        //uni番目の街に対応させる
        //uniは1-beginに注意
        int i,j;
        Croad.res(kyonum);
        Crroad.res(kyonum);
        for(i=0;i<n;i++){
            for(j=0;j<road[i].size();j++){if(uni[i]!=uni[road[i][j]]){Croad[uni[i]].pub(uni[road[i][j]]);}}
            for(j=0;j<rroad[i].size();j++){if(uni[i]!=uni[rroad[i][j]]){Crroad[uni[i]].pub(uni[rroad[i][j]]);}}
        }
        for(i=1;i<kyonum;i++){
            sort(Croad[i].begin(),Croad[i].end());
            unique(Croad[i].begin(),Croad[i].end());
            sort(Crroad[i].begin(),Crroad[i].end());
            unique(Crroad[i].begin(),Crroad[i].end());
        }
        return;
    }
};
class SAT_2{
    /*
    2-SATします。
    iの否定はi+nです.
    do_sat();で解きます.
    
    */
public:
    
    int n;
    SCC logic;
        SAT_2(int in){n=in;logic.road.res(2*n);logic.rroad.res(2*n);}
    int Not(int in){if(in<n){return in+n;}else{return in-n;}}
    
    void add_sat(int a,int b){//aならばb,bでないならばaでない
        logic.add_road(a,b);
        logic.add_road(Not(b),Not(a));
    }
    void waru_sat(int a,int b){add_sat(a,Not(b));}
    //aとbは同時に成り立たない
    pair<bool,vector<bool>> do_sat(void){
        logic.do_scc();
        vector<bool>ans(n);
        for(int i=0;i<n;i++){
            if(logic.uni[i]==logic.uni[Not(i)]){return mp(false,ans);}
            ans[i]=logic.uni[i]>logic.uni[Not(i)];
        }
        return mp(true,ans);
    }
};
int main(void){
    int n,m,i,j,q,w;cin>>n>>m;
    SAT_2 sat(n);
    vector<pair<int,int>>brk(n);
    pair<bool,vector<bool>> mpans;
    for(i=0;i<n;i++){
        cin>>q>>w;
        brk[i]=mp(q,w);
    }
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(brk[i].sec<brk[j].fir){continue;}
            if(brk[j].sec<brk[i].fir){continue;}
            sat.waru_sat(i,j);
            sat.waru_sat(i+n,j+n);
        }
    }
    
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(m-1-brk[i].fir<brk[j].fir){continue;}
            if(brk[j].sec<m-1-brk[i].sec){continue;}
            sat.waru_sat(i,j+n);
            sat.waru_sat(i+n,j);
        }
    }
    mpans=sat.do_sat();
    if(mpans.fir){cout<<"YES"<<endl;}
    else{cout<<"NO"<<endl;}
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX