結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー ks115
提出日時 2021-08-12 23:39:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 4,134 bytes
コンパイル時間 2,604 ms
コンパイル使用メモリ 211,936 KB
最終ジャッジ日時 2025-01-23 17:48:29
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

class StronglyConnectedComponents {
   public:
    StronglyConnectedComponents(vector<vector<int>> &G) {
        vector<int> postorder;
        vector<bool> visited(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            if (visited[i]) continue;
            dfs(G, visited, postorder, i);
        }

        rg.resize(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            for (auto g : G[i]) rg[g].push_back(i);
        }

        c = 0;
        _id.resize(G.size(), 0);
        for (int i = (int)G.size() - 1; i >= 0; i--) {
            if (_id[postorder[i]]) continue;
            vector<int> components;
            rdfs(rg, components, postorder[i], ++c);
            scc.push_back(components);
        }
    }

    int size() {
        return c;
    }

    int id(int u) {
        return _id[u];
    }

    bool same(int u, int v) {
        return _id[u] == _id[v];
    }

    vector<vector<int>> reverseGraph() {
        return rg;
    }

    vector<vector<int>> getComponents() {
        return scc;
    }
   
   private:
    int c;
    vector<int> _id;
    vector<vector<int>> rg, scc;

    void dfs(vector<vector<int>> &G, vector<bool> &visited, vector<int> &postorder, int v) {
        visited[v] = true;
        for (auto g : G[v]) {
            if (visited[g]) continue;
            dfs(G, visited, postorder, g);
        }
        postorder.push_back(v);
    }

    void rdfs(vector<vector<int>> &G, vector<int> &components, int v, int c) {
        _id[v] = c; components.push_back(v);
        for (auto g : G[v]) {
            if (_id[g]) continue;
            rdfs(G, components, g, c);
        }
    }
};

class TwoSat {
   private:
    const int sz;
    vector<int> b;
    vector<vector<int>> G;
    StronglyConnectedComponents *scc;

   public:
    TwoSat(int n) : sz(n), b(sz), G(2 * sz) {}

    void addEdge(int u, bool notu, int v, bool notv) {
        int u0 = notu ? u + sz : u;
        int u1 = notu ? u : u + sz;
        int v0 = notv ? v + sz : v;
        int v1 = notv ? v : v + sz;
        G[u1].push_back(v0);
        G[v1].push_back(u0);
    }

    bool isSatisfiable() {
        scc = new StronglyConnectedComponents(G);
        for (int i = 0; i < sz; i++) {
            if (scc->same(i, i + sz)) return false;
        } 
        return true;
    }

    vector<int> & assign() {
        for (int i = 0; i < sz; i++) {
            b[i] = scc->id(i) > scc->id(i + sz);
        }
        return b;
    }

};

int main() {
    int N; cin >> N;
    vector<string> U(N);
    for (auto &u : U) cin >> u;

    if (N > 52) {
        cout << "Impossible" << endl;
        return 0;
    }    

    auto same = [](string s, bool ls, string t, bool lt) -> bool {
        vector<string> strs(4);
        strs[0] = ls ? s.substr(0, 1) : s.substr(0, 2);
        strs[1] = ls ? s.substr(1, 2) : s.substr(2, 1);
        strs[2] = lt ? t.substr(0, 1) : t.substr(0, 2);
        strs[3] = lt ? t.substr(1, 2) : t.substr(2, 1);
        REP(i, 0, 4) REP(j, i + 1, 4) if (strs[i] == strs[j]) return true;
        return false;
    };

    TwoSat ts(N);
    REP(i, 0, N) {
        REP(j, i + 1, N) {
            if (same(U[i], true, U[j], true)) {
                ts.addEdge(i, true, j, true);
            }
            if (same(U[i], true, U[j], false)) {
                ts.addEdge(i, true, j, false);
            }
            if (same(U[i], false, U[j], true)) {
                ts.addEdge(i, false, j, true);
            }
            if (same(U[i], false, U[j], false)) {
                ts.addEdge(i, false, j, false);
            }
        }
    }

    if (!ts.isSatisfiable()) {
        cout << "Impossible" << endl;
        return 0;
    }

    auto assigned = ts.assign();
    REP(i, 0, N) {
        string l = assigned[i] ? U[i].substr(0, 1) : U[i].substr(0, 2);
        string r = assigned[i] ? U[i].substr(1, 2) : U[i].substr(2, 1);
        cout << l << " " << r << endl;
    }
    return 0;
}
0