結果

問題 No.1078 I love Matrix Construction
ユーザー kappybarkappybar
提出日時 2020-06-13 18:34:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 2,000 ms
コード長 2,726 bytes
コンパイル時間 1,918 ms
コンパイル使用メモリ 177,444 KB
実行使用メモリ 50,152 KB
最終ジャッジ日時 2024-06-25 17:48:27
合計ジャッジ時間 7,048 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
28,612 KB
testcase_01 AC 15 ms
28,844 KB
testcase_02 AC 33 ms
32,012 KB
testcase_03 AC 87 ms
37,008 KB
testcase_04 AC 123 ms
39,792 KB
testcase_05 AC 104 ms
38,120 KB
testcase_06 AC 34 ms
32,068 KB
testcase_07 AC 21 ms
30,052 KB
testcase_08 AC 102 ms
38,388 KB
testcase_09 AC 18 ms
29,200 KB
testcase_10 AC 245 ms
50,152 KB
testcase_11 AC 126 ms
40,428 KB
testcase_12 AC 195 ms
46,444 KB
testcase_13 AC 227 ms
48,428 KB
testcase_14 AC 157 ms
43,220 KB
testcase_15 AC 220 ms
47,560 KB
testcase_16 AC 21 ms
29,648 KB
testcase_17 AC 15 ms
28,640 KB
testcase_18 AC 29 ms
31,040 KB
testcase_19 AC 53 ms
34,132 KB
testcase_20 AC 52 ms
33,860 KB
testcase_21 AC 16 ms
28,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int n = 250005;
int c = 0;
vector<vector<int>> graph(2*n,vector<int>());
vector<vector<int>> revgraph(2*n,vector<int>());
vector<bool> seen(2*n,false);
vector<int> postorder;
vector<int> sccgroup(2*n,-1);

void dfs(int i){
    seen[i] = true;
    for(int v:graph[i]){
        if(seen[v]) continue;
        dfs(v);
    }
    postorder.push_back(i);
}

void revdfs(int i){
    sccgroup[i] = c;
    seen[i] = true;
    for(int v:revgraph[i]){
        if(seen[v]) continue;
        revdfs(v);
    }
}

void scc(){
    for(int i=0;i<2*n;i++){
        if(!seen[i]) dfs(i);
    }

    rep(i,2*n) seen[i] = false;
    for(int i=2*n-1;i>=0;i--){
        if(!seen[postorder[i]]){
            revdfs(postorder[i]);
            ++c;
        }
    }
}

vector<int> sat(){
    rep(i,n){
        if(sccgroup[i] == sccgroup[i+n]){
            return {};
        }
    }

    vector<int> res(n,false);
    rep(i,n){
        if(sccgroup[i] > sccgroup[i+n]) res[i] = true;
    }

    return res;
}

int main(){
    int m;
    cin >> m;
    n = m * m;
    vector<int> s(m),t(m),u(m);
    rep(i,m) cin >> s[i], --s[i];
    rep(i,m) cin >> t[i], --t[i];
    rep(i,m) cin >> u[i];

    rep(i,m){
        rep(j,m){
            int p = s[i] * m + j,q = j * m + t[i];

            if(u[i]==0){
                graph[p+n].push_back(q);
                graph[q+n].push_back(p);
                revgraph[p].push_back(q+n);
                revgraph[q].push_back(p+n);
            }else if(u[i]==1){
                graph[p].push_back(q);
                graph[q+n].push_back(p+n);
                revgraph[p+n].push_back(q+n);
                revgraph[q].push_back(p);
            }else if(u[i]==2){
                graph[p+n].push_back(q+n);
                graph[q].push_back(p);
                revgraph[p].push_back(q);
                revgraph[q+n].push_back(p+n);
            }else{
                graph[p].push_back(q+n);
                graph[q].push_back(p+n);
                revgraph[p+n].push_back(q);
                revgraph[q+n].push_back(p);
            }
        }
    }

    scc();
    vector<int> SAT = sat();
    if(SAT.size() == 0){
        cout << -1 << endl;
        return 0;
    }

    rep(i,n){
        cout << SAT[i] << " ";
        if(i%m==m-1) cout << endl;
    }

    /*
    rep(i,m)rep(j,m){
        if(SAT[s[i]*m+j] + SAT[j*m+t[i]] == u[i]){
            assert(false);
        }
    }
    */

    return 0;
}
0