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

提出ソース

結果

問題	No.274 The Wall
ユーザー	tsutaj
提出日時	2019-07-09 23:15:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	6,470 bytes
コンパイル時間	1,145 ms
コンパイル使用メモリ	97,016 KB
実行使用メモリ	576,768 KB
最終ジャッジ日時	2024-10-12 19:27:39
合計ジャッジ時間	4,800 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	400 ms 242,304 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	MLE	-
testcase_12	AC	22 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	7 ms 5,248 KB
testcase_15	AC	15 ms 5,248 KB
testcase_16	AC	272 ms 137,216 KB
testcase_17	AC	244 ms 130,304 KB
testcase_18	AC	272 ms 141,696 KB
testcase_19	AC	25 ms 6,820 KB
testcase_20	AC	29 ms 6,820 KB
testcase_21	AC	30 ms 6,816 KB
testcase_22	AC	31 ms 6,816 KB
testcase_23	AC	32 ms 6,816 KB
testcase_24	AC	32 ms 6,820 KB
testcase_25	AC	31 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <vector>
#include <iostream>
#include <cstdio>
#include <utility>
#include <tuple>
#include <algorithm>
using namespace std;

// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;

// 強連結成分分解
// Verified: AOJ GRL_3_C (Strongly Connected Components)
// Verified: ARC030 C (有向グラフ) ← 強連結を潰したグラフの構築の検証

// これは 2 回の DFS によって実現できる。
// はじめに普通の DFS をするが、その時に帰りがけ順に頂点番号の配列を作る。
// 次に、元のグラフの逆辺のみで構成されたグラフに対して、
// 帰りがけ順が遅かったものから順に DFS を行う。
// 帰りかけが遅かった頂点ほど、 DAG の先頭の強連結成分に属しているため、
// 辺を逆向きにすると、先頭の強連結成分から外に出られなくなることを利用している。

template <typename T = int>
struct GraphSCC {
public:
    const int n;
    vector<bool> isthrough;
    vector<int> vs, cmp;
    vector< vector< Edge<T> > > G, rG; // グラフ、逆辺グラフ
    vector< vector<int> > H; // 縮約後のグラフ

    GraphSCC(vector< vector< Edge<T> > > &_G) :
        n(_G.size()), isthrough(n, false), cmp(n, 0), G(_G), rG(n) {
            // 逆辺グラフ
            for(int i=0; i<n; i++) for(size_t j=0; j<G[i].size(); j++)
                rG[ G[i][j].to ].push_back(Edge<T>(i, G[i][j].cost));
        }

    void SCC_dfsone(int cur) {
        isthrough[cur] = true;
        for(size_t i=0; i<G[cur].size(); i++) {
            if(!isthrough[G[cur][i].to]) {
                SCC_dfsone(G[cur][i].to);
            }
        }
        vs.push_back(cur);
    }

    void SCC_dfstwo(vector<int> &vec, int cur, int k) {
        cmp[cur] = k;
        isthrough[cur] = true;
        vec.push_back(cur);
        for(size_t i=0; i<rG[cur].size(); i++) {
            if(!isthrough[rG[cur][i].to]) {
                SCC_dfstwo(vec, rG[cur][i].to, k);
            }
        }
    }

    // 縮約後のグループ、グループ数
    pair<vector<int>, int> scc() {
        // 1回めのDFS
        for(int i=0; i<n; i++)
            if(!isthrough[i]) SCC_dfsone(i);

        fill(isthrough.begin(), isthrough.end(), false);
        reverse(vs.begin(), vs.end());
        int k = 0; vector< vector<int> > S;

        // 2回めのDFS
        for(size_t i=0; i<vs.size(); i++) {
            if(!isthrough[vs[i]]) {
                S.push_back(vector<int>());
                SCC_dfstwo(S.back(), vs[i], k++);
            }
        }

        H.resize(k);
        fill(isthrough.begin(), isthrough.end(), false);
        for(size_t i=0; i<k; i++) {
            for(size_t j=0; j<S[i].size(); j++) {
                int v = S[i][j];
                for(size_t x=0; x<G[v].size(); x++) {
                    int u = G[v][x].to;
                    if(isthrough[cmp[u]] || cmp[v] == cmp[u]) continue;
                    isthrough[cmp[u]] = true;
                    H[cmp[v]].push_back(cmp[u]);
                }
            }
            for(size_t j=0; j<H[i].size(); j++) isthrough[ H[i][j] ] = false;
        }
        return make_pair(cmp, k);
    }
};

// クロージャ内にあるリテラルの数が高々 2 であるときの充足可能性問題 (2-SAT)
// 依存ライブラリ: SCC (graph_010_scc.cpp)
struct TwoSAT {
    int N; Graph<> G;
    TwoSAT(int N_) : N(N_), G(2*N_) {}
    int neg(int k) { return (k+N) % (2*N); }
    void add_edge(int u, int v) {
        G[u].emplace_back(v);
    }
    void add_AorB(int a, int b) {
        // (a or b) -> (na => b) and (nb => a)
        add_edge(neg(a), b);
        add_edge(neg(b), a);
    }
    void add_NAorB(int a, int b) {
        // (na or b) -> (a => b) and (nb => na)
        add_edge(a, b);
        add_edge(neg(b), neg(a));
    }
    void add_AorNB(int a, int b) {
        // (a or nb) -> (na => nb) and (b => a)
        add_edge(neg(a), neg(b));
        add_edge(b, a);
    }
    void add_NAorNB(int a, int b) {
        // (na or nb) -> (a => nb) and (b => na)
        add_edge(a, neg(b));
        add_edge(b, neg(a));
    }
    vector<int> build() {
        GraphSCC<> scc(G);
        vector<int> group, res(N); int K;
        tie(group, K) = scc.scc();
        for(int i=0; i<N; i++) {
            if(group[i] == group[N+i]) return {};
            res[i] = (group[i] > group[N+i]);
        }
        return res;
    }
};

void yuki_274() {
    int N, M; scanf("%d%d", &N, &M);
    vector<int> L(N), R(N);

    auto flip = [&](int l, int r) {
        return make_pair(M - 1 - r, M - 1 - l);
    };

    auto intersect = [&](int al, int ar, int bl, int br) {
        return !(ar < bl or br < al);
    };
    
    for(int i=0; i<N; i++) {
        scanf("%d%d", &L[i], &R[i]);
    }

    TwoSAT tsat(N);
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<N; j++) {
            for(int bit=0; bit<4; bit++) {
                int al = L[i], ar = R[i];
                int bl = L[j], br = R[j];
                if(bit & 1) tie(al, ar) = flip(al, ar);
                if(bit & 2) tie(bl, br) = flip(bl, br);

                if(intersect(al, ar, bl, br)) {
                    switch(bit) {
                    case 0:
                        // A and B はダメ -> NA or NB
                        tsat.add_NAorNB(i, j);
                        break;
                    case 1:
                        // NA and B はダメ -> A or NB
                        tsat.add_AorNB(i, j);
                        break;
                    case 2:
                        // A and NB はダメ -> NA or B
                        tsat.add_NAorB(i, j);
                        break;
                    case 3:
                        // NA and NB はダメ -> A or B
                        tsat.add_AorB(i, j);
                        break;
                    }
                }
            }
        }
    }
    auto res = tsat.build();
    if(res.size() == N) puts("YES");
    else puts("NO");
}

int main() {
    yuki_274();
    return 0;
}

yukicoder

結果

テストケース

ソースコード