結果

問題 No.1078 I love Matrix Construction
ユーザー kappybarkappybar
提出日時 2020-06-13 18:34:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 221 ms / 2,000 ms
コード長 2,726 bytes
コンパイル時間 1,861 ms
コンパイル使用メモリ 174,440 KB
実行使用メモリ 49,792 KB
最終ジャッジ日時 2023-09-08 00:39:03
合計ジャッジ時間 6,796 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
28,304 KB
testcase_01 AC 14 ms
28,372 KB
testcase_02 AC 34 ms
31,852 KB
testcase_03 AC 75 ms
36,636 KB
testcase_04 AC 108 ms
39,544 KB
testcase_05 AC 102 ms
38,060 KB
testcase_06 AC 32 ms
32,120 KB
testcase_07 AC 20 ms
29,864 KB
testcase_08 AC 90 ms
37,940 KB
testcase_09 AC 18 ms
29,064 KB
testcase_10 AC 221 ms
49,792 KB
testcase_11 AC 113 ms
40,136 KB
testcase_12 AC 174 ms
46,052 KB
testcase_13 AC 204 ms
48,200 KB
testcase_14 AC 146 ms
42,800 KB
testcase_15 AC 187 ms
47,252 KB
testcase_16 AC 20 ms
29,560 KB
testcase_17 AC 15 ms
28,480 KB
testcase_18 AC 29 ms
30,868 KB
testcase_19 AC 50 ms
33,724 KB
testcase_20 AC 51 ms
33,764 KB
testcase_21 AC 16 ms
28,460 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