結果

問題 No.470 Inverse S+T Problem
ユーザー rpy3cpp
提出日時 2019-05-19 17:26:26
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 4 ms
コード長 4,216 Byte
コンパイル時間 1,802 ms
使用メモリ 1,532 KB
最終ジャッジ日時 2019-08-27 14:59:46

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00sample1.txt AC 3 ms
1,504 KB
00sample2.txt AC 2 ms
1,508 KB
00sample3.txt AC 3 ms
1,500 KB
00sample4.txt AC 3 ms
1,500 KB
10hand01.txt AC 3 ms
1,496 KB
10hand02.txt AC 3 ms
1,496 KB
20randomA00.txt AC 3 ms
1,492 KB
20randomA01.txt AC 3 ms
1,492 KB
20randomA02.txt AC 3 ms
1,492 KB
30randomB00.txt AC 3 ms
1,500 KB
30randomB01.txt AC 3 ms
1,512 KB
30randomB02.txt AC 3 ms
1,520 KB
40randomC00.txt AC 3 ms
1,500 KB
40randomC01.txt AC 3 ms
1,504 KB
40randomC02.txt AC 3 ms
1,520 KB
50randomD00.txt AC 4 ms
1,528 KB
50randomD01.txt AC 3 ms
1,508 KB
50randomD02.txt AC 3 ms
1,512 KB
50randomD03.txt AC 3 ms
1,508 KB
50randomD04.txt AC 3 ms
1,520 KB
50randomD05.txt AC 3 ms
1,500 KB
90special01.txt AC 3 ms
1,504 KB
90special02.txt AC 4 ms
1,508 KB
90special03.txt AC 3 ms
1,516 KB
90special04.txt AC 3 ms
1,532 KB
95challenge01.txt AC 3 ms
1,520 KB
95challenge02.txt AC 3 ms
1,528 KB
95challenge03.txt AC 3 ms
1,524 KB
99_system_test1.txt AC 3 ms
1,488 KB
99_system_test2.txt AC 3 ms
1,492 KB
99_system_test3.txt AC 3 ms
1,492 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
using namespace std;

class SCC{
private:
    int nV;
    vector<vector<int>> G;
    vector<vector<int>> rG;
    vector<int> vs;
    vector<bool> used;
    void dfs(int v){
        used[v] = true;
        for (auto u: G[v]) if (not used[u]) dfs(u);
        vs.push_back(v);
    }
    void rdfs(int v, int k){
        used[v] = true;
        cmp[v] = k;
        for (auto u: rG[v]) if (not used[u]) rdfs(u, k);
    }
public:
    vector<int> cmp;
    SCC(const vector<vector<int>>& _G):
        nV(_G.size()), G(_G), rG(nV,vector<int>()), vs(), used(nV, false), cmp(nV, 0){
        for (int from = 0; from < nV; ++from) for (auto to : G[from]) rG[to].push_back(from);
        for (int v = 0; v < nV; ++v) if (not used[v]) dfs(v);
        used.assign(nV, false);
        int k = 0;
        for (auto rit = vs.rbegin(); rit != vs.rend(); ++rit){
            if (not used[*rit]) rdfs(*rit, k++);
        }
    }
};

pair<bool, vector<bool>> TwoSAT(const vector<vector<int>> &Es){
    // vertex 0..n-1   : variable[i] = true
    // vertex n..2*n-1 : variable[i] = false
    // return value: bool: 2SAT can be satisfied or not
    // return value: vector<bool>: One solution which satisfies the SAT.
    assert(Es.size() % 2 == 0);
    int n = Es.size() / 2;
    vector<bool> sol(n, false);
    SCC scc(Es);
    for (int i = 0; i < n; ++i) if (scc.cmp[i] == scc.cmp[i + n]) return make_pair(false, sol);
    for (int i = 0; i < n; ++i) sol[i] = scc.cmp[i] > scc.cmp[i + n];
    return make_pair(true, sol);
}

int main(){
    int N;
    cin >> N;
    if (N > 52){
        cout << "Impossible" << endl;
        return 0;
    }
    vector<string> Us(N);
    for (auto &U : Us) cin >> U;
    vector<vector<int>> Es(2 * N, vector<int>());
    for (int i = 0; i < N - 1; ++i){
        char a = Us[i][0];
        char b = Us[i][1];
        char c = Us[i][2];
        for (int j = i + 1; j < N; ++j){
            char d = Us[j][0];
            char e = Us[j][1];
            char f = Us[j][2];
            // a + bc と分割するとき(頂点 i に対応)
            // d + ef と分割したときに重複が発生するか否か
            if ((a == d) or (b == e and c == f)){ // 重複する場合
                Es[i].push_back(j + N);           // a+bc としたならば de+f とすることが必要
                Es[j].push_back(i + N);           // d+ef としたならば ab+c とすることが必要
            }
            // a + bc と分割するとき(頂点 i に対応)
            // de + f と分割したときに重複が発生するか否か
            if ((a == f) or (b == d and c == e)){ // 重複する場合
                Es[i].push_back(j);               // a+bc としたならば d+ef とすることが必要
                Es[j + N].push_back(i + N);       // de+f としたならば ab+c とすることが必要
            }
            // ab + c と分割するとき(頂点 i に対応)
            // d + ef と分割したときに重複が発生するか否か
            if ((c == d) or (a == e and b == f)){ // 重複する場合
                Es[i + N].push_back(j + N);       // ab+c としたならば de+f とすることが必要
                Es[j].push_back(i);               // d+ef としたならば a+bc とすることが必要
            }
            // ab + c と分割するとき(頂点 i に対応)
            // de + f と分割したときに重複が発生するか否か
            if ((c == f) or (a == d and b == e)){ // 重複する場合
                Es[i + N].push_back(j);           // ab+c としたならば d+ef とすることが必要
                Es[j + N].push_back(i);           // de+f としたならば a+bc とすることが必要
            }
        }
    }
    auto result = TwoSAT(Es);
    if (result.first == false){
        cout << "Impossible" << endl;
    }else{
        int i = 0;
        for (auto tf: result.second){
            if (tf){
                cout << Us[i][0] << ' ' << Us[i][1] << Us[i][2] << '\n';
            }else{
                cout << Us[i][0] << Us[i][1] << ' ' << Us[i][2] << '\n';
            }
            ++i;
        }
    }
    return 0;
}
0