結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー rpy3cpp
提出日時 2019-05-19 17:26:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,216 bytes
コンパイル時間 2,176 ms
コンパイル使用メモリ 187,140 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-22 13:53:09
合計ジャッジ時間 3,514 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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