結果

問題 No.1078 I love Matrix Construction
ユーザー ks115ks115
提出日時 2021-08-14 15:58:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 328 ms / 2,000 ms
コード長 3,880 bytes
コンパイル時間 2,912 ms
コンパイル使用メモリ 210,200 KB
実行使用メモリ 73,248 KB
最終ジャッジ日時 2024-04-15 13:58:05
合計ジャッジ時間 8,459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 38 ms
15,048 KB
testcase_03 AC 113 ms
32,632 KB
testcase_04 AC 158 ms
40,364 KB
testcase_05 AC 139 ms
34,052 KB
testcase_06 AC 33 ms
13,256 KB
testcase_07 AC 11 ms
7,020 KB
testcase_08 AC 131 ms
34,084 KB
testcase_09 AC 6 ms
5,376 KB
testcase_10 AC 328 ms
73,248 KB
testcase_11 AC 170 ms
42,248 KB
testcase_12 AC 266 ms
61,572 KB
testcase_13 AC 302 ms
68,544 KB
testcase_14 AC 205 ms
53,200 KB
testcase_15 AC 293 ms
64,976 KB
testcase_16 AC 10 ms
6,380 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 25 ms
10,712 KB
testcase_19 AC 71 ms
20,356 KB
testcase_20 AC 67 ms
19,964 KB
testcase_21 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

class StronglyConnectedComponents {
   public:
    StronglyConnectedComponents(vector<vector<int>> &G) {
        vector<int> postorder;
        vector<bool> visited(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            if (visited[i]) continue;
            dfs(G, visited, postorder, i);
        }

        rg.resize(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            for (auto g : G[i]) rg[g].push_back(i);
        }

        c = 0;
        _id.resize(G.size(), 0);
        for (int i = (int)G.size() - 1; i >= 0; i--) {
            if (_id[postorder[i]]) continue;
            vector<int> components;
            rdfs(rg, components, postorder[i], ++c);
            scc.push_back(components);
        }
    }

    int size() {
        return c;
    }

    int id(int u) {
        return _id[u];
    }

    bool same(int u, int v) {
        return _id[u] == _id[v];
    }

    vector<vector<int>> reverseGraph() {
        return rg;
    }

    vector<vector<int>> getComponents() {
        return scc;
    }
   
   private:
    int c;
    vector<int> _id;
    vector<vector<int>> rg, scc;

    void dfs(vector<vector<int>> &G, vector<bool> &visited, vector<int> &postorder, int v) {
        visited[v] = true;
        for (auto g : G[v]) {
            if (visited[g]) continue;
            dfs(G, visited, postorder, g);
        }
        postorder.push_back(v);
    }

    void rdfs(vector<vector<int>> &G, vector<int> &components, int v, int c) {
        _id[v] = c; components.push_back(v);
        for (auto g : G[v]) {
            if (_id[g]) continue;
            rdfs(G, components, g, c);
        }
    }
};

class TwoSat {
   private:
    const int sz;
    vector<int> b;
    vector<vector<int>> G;
    StronglyConnectedComponents *scc;

   public:
    TwoSat(int n) : sz(n), b(sz), G(2 * sz) {}

    void addEdge(int u, bool notu, int v, bool notv) {
        int u0 = notu ? u + sz : u;
        int u1 = notu ? u : u + sz;
        int v0 = notv ? v + sz : v;
        int v1 = notv ? v : v + sz;
        G[u1].push_back(v0);
        G[v1].push_back(u0);
    }

    bool isSatisfiable() {
        scc = new StronglyConnectedComponents(G);
        for (int i = 0; i < sz; i++) {
            if (scc->same(i, i + sz)) return false;
        } 
        return true;
    }

    vector<int> & assign() {
        for (int i = 0; i < sz; i++) {
            b[i] = scc->id(i) > scc->id(i + sz);
        }
        return b;
    }

};

int main() {
    int N; cin >> N;
    vector<int> S(N), T(N), U(N);
    for (auto &v : S) cin >> v;
    for (auto &v : T) cin >> v;
    for (auto &v : U) cin >> v;

    vector<vector<int>> SI(N);
    REP(i, 0, N) SI[S[i] - 1].push_back(i);

    auto decode = [N](int v) -> pair<int, int> {
        return {v / N, v % N};
    };

    auto encode = [N](int x, int y) -> int {
        return x * N + y;
    };

    TwoSat ts(N * N);

    REP(i, 0, N * N) {
        auto [x, y] = decode(i);
        for (auto &j : SI[x]) {
            int k = encode(y, T[j] - 1);
            if (U[j] == 0) {
                ts.addEdge(i, false, k, false);
            } else if (U[j] == 1) {
                ts.addEdge(i, true, k, false);
            } else if (U[j] == 2) {
                ts.addEdge(i, false, k, true);
            } else if (U[j] == 3) {
                ts.addEdge(i, true, k, true);
            }
        }
    }

    if (!ts.isSatisfiable()) {
        cout << -1 << endl;
        return 0;
    }

    auto assigned = ts.assign();
    REP(i, 0, N) {
        REP(j, 0, N) {
            if (assigned[encode(i, j)]) cout << 1 << " ";
            else cout << 0 << " ";
        }
        cout << endl;
    }

    return 0;
}
0