結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー pekempey
提出日時 2016-12-20 01:22:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 225 ms / 2,000 ms
コード長 3,210 bytes
コンパイル時間 2,630 ms
コンパイル使用メモリ 191,576 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-12-22 13:15:07
合計ジャッジ時間 3,968 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct SCC {
    vector<vector<int>> G, rG, H, cc;
    vector<int> cid, ord, vis;
    int n;
    SCC(int n) : n(n), G(n), rG(n), vis(n), cid(n, -1) {}
    void add(int u, int v) {
        G[u].push_back(v);
        rG[v].push_back(u);
    }
    void buildLight() {
        for (int i = 0; i < n; i++) if (!vis[i]) dfs(i);
        int k = 0;
        for (int i = n - 1; i >= 0; i--) if (cid[ord[i]] == -1) dfs2(ord[i], k++);
        cc.resize(k);
        for (int i = 0; i < n; i++) cc[cid[i]].push_back(i);
    }
    void build() {
        buildLight();
        set<pair<int, int>> es;
        for (int i = 0; i < n; i++) for (int j : G[i]) if (cid[i] != cid[j]) es.emplace(cid[i], cid[j]);
        H.resize(cc.size());
        for (auto e : es) H[e.first].push_back(e.second);
    }
    void dfs(int curr) {
        vis[curr] = true;
        for (int next : G[curr]) if (!vis[next]) dfs(next);
        ord.push_back(curr);
    }
    void dfs2(int curr, int k) {
        cid[curr] = k;
        for (int next : rG[curr]) if (cid[next] == -1) dfs2(next, k);
    }
    int size() { return H.size(); }
    vector<int> &operator[](int k) { return H[k]; }
};

struct SAT2 {
    SCC scc;
    vector<bool> var;
    bool satisfiable;

    SAT2(int n) : scc(n * 2), var(n) {}

    // i or j
    void add(int i, int ii, int j, int jj) {
        scc.add(i * 2 + 1 - ii, j * 2 + jj);
        scc.add(j * 2 + 1 - jj, i * 2 + ii);
    }

    bool isSatisfiable() {
        return satisfiable;
    }

    void build() {
        scc.build();
        satisfiable = true;
        for (int i = 0; i < var.size(); i++) {
            if (scc.cid[i * 2] == scc.cid[i * 2 + 1]) {
                satisfiable = false;
            }
            var[i] = scc.cid[i * 2] < scc.cid[i * 2 + 1];
        }
    }

    bool operator[](int k) {
        return var[k];
    }
};

int main() {
    int n;
    cin >> n;

    if (n >= 3000) {
        puts("Impossible");
        return 0;
    }

    vector<string> s(n);
    SAT2 sat(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            string a = s[i];
            string b = s[j];
            if (a.substr(0, 1) == b.substr(0, 1) || a.substr(1, 2) == b.substr(1, 2)) {
                sat.add(i, true, j, true);
            }
            if (a.substr(0, 1) == b.substr(2, 1) || a.substr(1, 2) == b.substr(0, 2)) {
                sat.add(i, true, j, false);
            }
            if (a.substr(0, 2) == b.substr(1, 2) || a.substr(2, 1) == b.substr(0, 1)) {
                sat.add(i, false, j, true);
            }
            if (a.substr(0, 2) == b.substr(0, 2) || a.substr(2, 1) == b.substr(2, 1)) {
                sat.add(i, false, j, false);
            }
        }
    }

    sat.build();

    if (!sat.isSatisfiable()) {
        puts("Impossible");
    } else {
        for (int i = 0; i < n; i++) {
            if (sat[i]) {
                cout << s[i].substr(0, 2) << " " << s[i].substr(2, 1) << endl;
            } else {
                cout << s[i].substr(0, 1) << " " << s[i].substr(1, 2) << endl;
            }
        }
    }
}
0