結果

問題 No.1078 I love Matrix Construction
ユーザー MisterMister
提出日時 2020-08-18 12:24:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 4,126 bytes
コンパイル時間 1,109 ms
コンパイル使用メモリ 92,680 KB
実行使用メモリ 95,720 KB
最終ジャッジ日時 2024-10-12 02:37:59
合計ジャッジ時間 6,291 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 34 ms
19,032 KB
testcase_03 AC 110 ms
39,892 KB
testcase_04 AC 155 ms
52,116 KB
testcase_05 AC 119 ms
44,484 KB
testcase_06 AC 34 ms
16,316 KB
testcase_07 AC 13 ms
8,312 KB
testcase_08 AC 122 ms
45,140 KB
testcase_09 AC 7 ms
6,820 KB
testcase_10 AC 299 ms
95,720 KB
testcase_11 AC 159 ms
54,600 KB
testcase_12 AC 263 ms
81,504 KB
testcase_13 AC 300 ms
90,992 KB
testcase_14 AC 204 ms
69,500 KB
testcase_15 AC 294 ms
84,952 KB
testcase_16 AC 11 ms
7,296 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 26 ms
13,128 KB
testcase_19 AC 62 ms
25,700 KB
testcase_20 AC 64 ms
25,412 KB
testcase_21 AC 3 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

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

template <class Cost = int>
struct Graph {
    std::vector<std::vector<Edge<Cost>>> graph;

    Graph(int n = 0) : graph(n) {}

    void span(bool direct, int src, int dst, Cost cost = 1) {
        graph[src].emplace_back(src, dst, cost);
        if (!direct) graph[dst].emplace_back(dst, src, cost);
    }

    int size() const { return graph.size(); }
    void clear() { graph.clear(); }
    void resize(int n) { graph.resize(n); }

    std::vector<Edge<Cost>>& operator[](int v) { return graph[v]; }
    std::vector<Edge<Cost>> operator[](int v) const { return graph[v]; }
};

template <class Cost = int>
struct StronglyConnectedComponents {
    Graph<Cost> graph, rgraph;
    std::vector<bool> visited;
    std::vector<int> stk;

    // id[v] = 頂点vはgroups[id[v]]に属する
    std::vector<int> id;
    std::vector<std::vector<int>> groups;

    explicit StronglyConnectedComponents(const Graph<Cost>& g)
        : graph(g), visited(graph.size(), false), id(graph.size(), -1) {
        revinit();

        for (int v = 0; v < (int)graph.size(); ++v) dfs(v);

        while (!stk.empty()) {
            int v = stk.back();
            stk.pop_back();
            if (id[v] < 0) {
                groups.emplace_back();
                rdfs(v);
            }
        }
    }

    void revinit() {
        rgraph = Graph<Cost>(graph.size());
        for (int v = 0; v < (int)graph.size(); ++v) {
            for (const auto& e : graph[v]) {
                rgraph[e.dst].emplace_back(e.dst, v, e.cost);
            }
        }
    }

    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (const auto& e : graph[v]) dfs(e.dst);
        stk.push_back(v);
    }

    void rdfs(int v) {
        if (id[v] >= 0) return;
        id[v] = groups.size() - 1;
        groups.back().push_back(v);
        for (const auto& e : rgraph[v]) rdfs(e.dst);
    }
};

struct TwoSat {
    int vnum;
    Graph<> graph;

    explicit TwoSat(int n) : vnum(n), graph(n * 2) {}

    // t=1 <=> true
    int enc(int x, bool t) {
        return x + (t ? vnum : 0);
    }

    // [tx]x V [ty]y
    void span(int x, bool tx, int y, bool ty) {
        graph[enc(x, !tx)].emplace_back(enc(x, !tx), enc(y, ty));
        graph[enc(y, !ty)].emplace_back(enc(y, !ty), enc(x, tx));
    }

    // if unsatisfiable, return an empty vector
    std::vector<bool> exec() {
        StronglyConnectedComponents scc(graph);

        std::vector<bool> assign(vnum);
        for (int x = 0; x < vnum; ++x) {
            int fid = scc.id[enc(x, false)],
                tid = scc.id[enc(x, true)];

            if (fid == tid) {
                assign.clear();
                break;
            } else {
                assign[x] = (fid < tid);
            }
        }
        return assign;
    }
};

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> ss(n), ts(n), us(n);
    for (auto& s : ss) {
        std::cin >> s;
        --s;
    }
    for (auto& t : ts) {
        std::cin >> t;
        --t;
    }
    for (auto& u : us) std::cin >> u;

    TwoSat sat(n * n);
    auto enc = [&](int x, int y) { return x * n + y; };

    for (int i = 0; i < n; ++i) {
        int p = us[i] & 1,
            q = us[i] >> 1;
        for (int j = 0; j < n; ++j) {
            sat.span(enc(ss[i], j), 1 - p, enc(j, ts[i]), 1 - q);
        }
    }

    auto ans = sat.exec();
    if (ans.empty()) {
        std::cout << -1 << "\n";
    } else {
        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < n; ++y) {
                std::cout << ans[enc(x, y)] << " ";
            }
            std::cout << "\n";
        }
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}
0