結果

問題 No.1078 I love Matrix Construction
ユーザー QCFium
提出日時 2020-05-02 17:17:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 2,000 ms
コード長 1,656 bytes
コンパイル時間 2,460 ms
コンパイル使用メモリ 180,000 KB
実行使用メモリ 48,340 KB
最終ジャッジ日時 2024-12-30 18:16:30
合計ジャッジ時間 7,040 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
int ri() {
    int n;
    scanf("%d", &n);
    return n;
}
std::vector<std::vector<int> > hen;
std::vector<std::vector<int> > rev;
std::vector<int> ord;
std::vector<bool> visited;
void dfs0(int i) {
    visited[i] = true;
    for (auto j : hen[i]) if (!visited[j]) dfs0(j);
    ord.push_back(i);
}
std::vector<int> group;
int group_cnt = 0;
void dfs1(int i) {
    group[i] = group_cnt;
    for (auto j : rev[i]) if (group[j] == -1) dfs1(j);
}
int main() {
    int n = ri();
    int a[n], b[n], c[n];
    for (auto &i : a) i = ri() - 1;
    for (auto &i : b) i = ri() - 1;
    for (auto &i : c) i = ri();
    hen.resize(n * n * 2);
    rev.resize(n * n * 2);
#define INDEX(i, j, k) (((i) * n + (j)) * 2 + k)
    for (int i = 0; i < n; i++) {
        bool r0 = c[i] & 1;
        bool r1 = c[i] >> 1;
        for (int j = 0; j < n; j++) {
            hen[INDEX(a[i], j, r0)].push_back(INDEX(j, b[i], !r1));
            rev[INDEX(j, b[i], !r1)].push_back(INDEX(a[i], j, r0));
            hen[INDEX(j, b[i], r1)].push_back(INDEX(a[i], j, !r0));
            rev[INDEX(a[i], j, !r0)].push_back(INDEX(j, b[i], r1));
        }
    }
    
    visited.resize(n * n * 2);
    for (int i = 0; i < n * n * 2; i++) if (!visited[i]) dfs0(i);
    std::reverse(ord.begin(), ord.end());
    group.resize(n * n * 2, -1);
    for (auto i : ord) if (group[i] == -1) {
        dfs1(i);
        group_cnt++;
    }
    bool possible = true;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        if (group[INDEX(i, j, 0)] == group[INDEX(i, j, 1)]) possible = false;
    if (!possible) puts("-1");
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++){
                if (j) printf(" ");
                printf("%d", group[INDEX(i, j, 0)] < group[INDEX(i, j, 1)]);
            }
            puts("");
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0