結果

問題 No.274 The Wall
ユーザー oyasoyas
提出日時 2017-05-14 09:28:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 3,928 bytes
コンパイル時間 964 ms
コンパイル使用メモリ 83,760 KB
実行使用メモリ 132,224 KB
最終ジャッジ日時 2024-06-22 02:16:28
合計ジャッジ時間 2,628 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 125 ms
70,016 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,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 392 ms
132,224 KB
testcase_12 AC 10 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 5 ms
6,940 KB
testcase_15 AC 10 ms
6,940 KB
testcase_16 AC 93 ms
38,784 KB
testcase_17 AC 85 ms
36,992 KB
testcase_18 AC 90 ms
39,936 KB
testcase_19 AC 17 ms
6,944 KB
testcase_20 AC 19 ms
6,944 KB
testcase_21 AC 20 ms
6,940 KB
testcase_22 AC 21 ms
6,944 KB
testcase_23 AC 21 ms
6,940 KB
testcase_24 AC 21 ms
6,940 KB
testcase_25 AC 21 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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

// 2sat.cpp
#include <vector>
#include <iostream>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef vector<int> vi;
// scc.cpp
// (Strongly Connected Component)
struct SCCGraph: public vector<vi> {
vector<int> order; // ()
vector<int> vs; //
vector<bool> used; // 調
using vector::vector; //
SCCGraph(const vector<vi> &v): vector::vector(v) {} // 使
// a -> b push_back()
void add_edge(int a, int b){
(*this)[a].push_back(b);
}
// scc()使
void dfs(int n, int k, vector<vi> &v, vector<vi> &rv){
used[n] = true;
order[n] = k;
for(auto t: v[n]){
if( !rv.empty() ) rv[t].push_back(n); //
if( !used[t] ) dfs(t, k, v, rv);
}
vs.push_back(n);
}
//
int scc(){
int N = size();
used.assign(N, false);
order.resize(N);
vs.clear();
vector<vi> rG(N), tmp; //
for(int n=0; n < N; n++){
if( !used[n] ) dfs(n, n, (*this), rG);
}
used.assign(N, false);
int k = 0; //
for(int i = vs.size()-1; i >= 0; i--){
if( !used[ vs[i] ] ) dfs(vs[i], k++, rG, tmp);
}
return k;
}
//
bool find(int x, int y){
return order[x] == order[y];
}
};
// scc使
vector<int> scc(const vector<vi> &v){
SCCGraph g(v);
g.scc();
return g.order;
}
// 2-SAT
struct TwoSAT {
SCCGraph graph;
int N;
TwoSAT(int n): graph( (n+1)*2 ) {
N = n;
}
// ( a -> b )(~a)
void add_edge(int a, int b){
if( a < 0 ) a = N - a;
if( b < 0 ) b = N - b;
graph.add_edge(a, b);
}
// ( a V b ) a,b(0)
void add_or(int a, int b){
//if( a < 0 ) a = graph.size() - a;
//if( b < 0 ) b = graph.size() - b;
//int na = (a + graph.size()) % (2*graph.size());
//int nb = (b + graph.size()) % (2*graph.size());
add_edge(-a, b);
add_edge(-b, a);
}
//
bool solve(){
graph.scc();
bool ret = true;
for(int i=1; i <= N; i++){
if( graph.order[i] == graph.order[N+i] ) ret = false;
}
return ret;
}
//
bool value(int a){
if( a < 0 ) a = N - a;
return graph.order[a] > graph.order[(N+a-1)%(2*N)+1];
}
};
// test
// yukicoder No.274 The Wall (http://yukicoder.me/problems/no/274)
int main(){
int N, M;
int L[2005], R[2005];
int rL[2005], rR[2005];
TwoSAT sat(2005);
// sat.add_or( 1, -2);
// sat.add_or( 2, 3);
// sat.add_or(-3, -1);
// cout << sat.solve() << endl;
// rep(i,3) cout << (sat.value(i+1) ? "true" : "false") << endl;
//
// return 0;
cin >> N >> M;
rep(i,N){
cin >> L[i] >> R[i];
rR[i] = M - L[i] - 1;
rL[i] = M - R[i] - 1;
//cout << "reverse: " << rL[i] << " " << rR[i] << endl;
}
//auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){
// if( (Lj <= Li && Li <= Rj) ||
// (Lj <= Ri && Ri <= Rj) ||
// (Li <= Lj && Lj <= Ri) ||
// (Li <= Rj && Rj <= Ri) ){
// sat.add_or( -a, -b );
// }
//};
auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){
if( !(Rj < Li || Ri < Lj) ){
sat.add_or( -a, -b );
}
};
rep(i,N) rep(j,i){
fn( L[i], L[j], R[i], R[j], (i+1), (j+1) );
fn( rL[i], L[j], rR[i], R[j], -(i+1), (j+1) );
fn( L[i], rL[j], R[i], rR[j], (i+1), -(j+1) );
fn( rL[i], rL[j], rR[i], rR[j], -(i+1), -(j+1) );
}
cout << (sat.solve() ? "YES" : "NO") << endl;
//rep(i,N) cout << sat.value(i+1) << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0