#495934 (C++17) No.1078 I love Matrix Construction

• 問題: No.1078 I love Matrix Construction
• ユーザー: kimiyuki
• 提出日時: 2020-06-12 22:00:58
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 261 ms / 2,000 ms
• コード長: 5,533 bytes
• コンパイル時間: 1,332 ms
• コンパイル使用メモリ: 109,896 KB
• 最終ジャッジ日時: 2025-01-11 02:34:31
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	AC * 22

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:44:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     std::vector<int> acc(n); {
      |            ~~~~~^~~~~~~~~~
main.cpp:47:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |             used[i] = true;
      |             ~^~~~~~~~~~~~~
main.cpp:52:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |         reverse(ALL(acc));
      |         ~~~~~^~~~~~~~~~~~~
main.cpp:57:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |         std::function<void (int)> rdfs = [&](int i) {
      |         ~~~~~^~~~~~~~~~~~~

ソースコード

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#line 1 "main.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1078"
#include <cassert>
#include <iostream>
#line 2 "/home/user/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 3 "/home/user/Library/utils/two_satisfiability.hpp"
#include <utility>
#include <vector>
#line 2 "/home/user/Library/graph/strongly_connected_components.hpp"
#include <functional>
#line 4 "/home/user/Library/graph/transpose_graph.hpp"
/**
 * @param g is an adjacent list of a digraph
 * @note $O(V + E)$
 * @see https://en.wikipedia.org/wiki/Transpose_graph
 */
std::vector<std::vector<int> > make_transpose_graph(std::vector<std::vector<int> > const & g) {
    int n = g.size();
    std::vector<std::vector<int> > h(n);
    REP (i, n) {
        for (int j : g[i]) {
            h[j].push_back(i);
        }
    }
    return h;
}
#line 7 "/home/user/Library/graph/strongly_connected_components.hpp"
/**
 * @brief strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解
 * @return the pair (the number k of components, the function from vertices of g to components)
 * @param g is an adjacent list of a digraph
 * @param g_rev is the transpose graph of g
 * @note $O(V + E)$
 */
std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g, const std::vector<std::vector
    <int> > & g_rev) {
    int n = g.size();
    std::vector<int> acc(n); {
        std::vector<bool> used(n);
        std::function<void (int)> dfs = [&](int i) {
            used[i] = true;
            for (int j : g[i]) if (not used[j]) dfs(j);
            acc.push_back(i);
        };
        REP (i,n) if (not used[i]) dfs(i);
        reverse(ALL(acc));
    }
    int size = 0;
    std::vector<int> component_of(n); {
        std::vector<bool> used(n);
        std::function<void (int)> rdfs = [&](int i) {
            used[i] = true;
            component_of[i] = size;
            for (int j : g_rev[i]) if (not used[j]) rdfs(j);
        };
        for (int i : acc) if (not used[i]) {
            rdfs(i);
            ++ size;
        }
    }
    return { size, move(component_of) };
}
std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g) {
    return decompose_to_strongly_connected_components(g, make_transpose_graph(g));
}
#line 6 "/home/user/Library/utils/two_satisfiability.hpp"
/**
 * @brief 2-SAT ($O(N)$)
 * @param n is the number of variables
 * @param cnf is a proposition in a conjunctive normal form. Each literal is expressed as number $x$ s.t. $1 \le \vert x \vert \le n$
 * @return a vector with the length $n$ if SAT. It's empty if UNSAT.
 */
std::vector<bool> compute_two_satisfiability(int n, const std::vector<std::pair<int, int> > & cnf) {
    // make digraph
    std::vector<std::vector<int> > g(2 * n);
    auto index = [&](int x) {
        assert (x != 0 and abs(x) <= n);
        return x > 0 ? x - 1 : n - x - 1;
    };
    for (auto it : cnf) {
        int x, y; std::tie(x, y) = it;  // x or y
        g[index(- x)].push_back(index(y));  // not x implies y
        g[index(- y)].push_back(index(x));  // not y implies x
    }
    // do SCC
    std::vector<int> component = decompose_to_strongly_connected_components(g).second;
    std::vector<bool> valuation(n);
    REP3 (x, 1, n + 1) {
        if (component[index(x)] == component[index(- x)]) {  // x iff not x
            return std::vector<bool>();  // unsat
        }
        valuation[x - 1] = component[index(x)] > component[index(- x)];  // use components which indices are large
    }
    return valuation;
}
#line 6 "main.cpp"
using namespace std;
vector<vector<bool> > solve(int n, vector<int> & s, vector<int> & t, vector<int> & u) {
    auto var = [&](int y, int x) { return y * n + x; };
    vector<pair<int, int> > cnf;
    REP (y, n) {
        REP (x, n) {
            int a = var(s[y], x) + 1;
            int b = var(x, t[y]) + 1;
            if (u[y] == 0) {
                cnf.emplace_back(a, b);
            } else if (u[y] == 1) {
                cnf.emplace_back(- a, b);
            } else if (u[y] == 2) {
                cnf.emplace_back(a, - b);
            } else if (u[y] == 3) {
                cnf.emplace_back(- a, - b);
            } else {
                assert (false);
            }
        }
    }
    auto ev = compute_two_satisfiability(n * n, cnf);
    if (ev.empty()) {
        return vector<vector<bool> >();
    } else {
        vector<vector<bool> > a(n, vector<bool>(n));
        REP (y, n) {
            REP (x, n) {
                a[y][x] = ev[var(y, x)];
            }
        }
        return a;
    }
}
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> s(n);
    REP (i, n) {
        scanf("%d", &s[i]);
        -- s[i];
    }
    vector<int> t(n);
    REP (i, n) {
        scanf("%d", &t[i]);
        -- t[i];
    }
    vector<int> u(n);
    REP (i, n) {
        scanf("%d", &u[i]);
    }
    // solve
    auto a = solve(n, s, t, u);
    // output
    if (a.empty()) {
        printf("%d\n", -1);
    } else {
        REP (y, n) {
            REP (x, n) {
                printf("%d%c", (int)a[y][x], x + 1 < n ? ' ' : '\n');
            }
        }
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX