結果

問題 No.470 Inverse S+T Problem
ユーザー pekempeypekempey
提出日時 2016-12-20 01:09:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,029 bytes
コンパイル時間 2,210 ms
コンパイル使用メモリ 187,860 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2024-06-01 22:29:14
合計ジャッジ時間 3,433 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
5,376 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 220 ms
6,912 KB
testcase_30 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class StronglyConnectedComponents {
private:
    const vector<vector<int>> &graph;
    vector<vector<int>> reversedGraph;
    vector<vector<int>> compressedGraph;
    vector<int> componentID;
    vector<int> postOrder;
    vector<bool> visited;
    stack<int> adjacent;

public:
    StronglyConnectedComponents(const vector<vector<int>> &graph) :
        graph(graph),
        reversedGraph(graph.size()),
        componentID(graph.size(), -1),
        visited(graph.size()) {
        for (int i = 0; i < graph.size(); i++) {
            for (int j : graph[i]) {
                reversedGraph[j].push_back(i);
            }
        }
        for (int i = 0; i < graph.size(); i++) {
            dfs(i);
        }
        reverse(postOrder.begin(), postOrder.end());
        for (int i : postOrder) {
            if (componentID[i] == -1) {
                dfs2(i);
                while (!adjacent.empty()) {
                    visited[adjacent.top()] = true;
                    adjacent.pop();
                }
                compressedGraph.emplace_back(vector<int>());
            }
        }
    }

    vector<vector<int>> &getCompressedGraph() {
        return compressedGraph;
    }

    int operator[](int u) {
        return componentID[u];
    }

private:
    void dfs(int u) {
        if (visited[u]) {
            return;
        }
        visited[u] = true;
        for (int v : graph[u]) {
            dfs(v);
        }
        postOrder.push_back(u);
    }

    void dfs2(int u) {
        componentID[u] = compressedGraph.size();
        for (int v : reversedGraph[u]) {
            if (componentID[v] == -1) {
                dfs2(v);
            } else if (componentID[v] != componentID[u] && visited[componentID[v]]) {
                compressedGraph[componentID[v]].push_back(componentID[u]);
                visited[componentID[v]] = false;
                adjacent.push(componentID[v]);
            }
        }
    }
};

struct SAT2 {
    vector<vector<int>> g;
    vector<bool> var;
    bool satisfiable;

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

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

    bool isSatisfiable() {
        return satisfiable;
    }

    void build() {
        StronglyConnectedComponents scc(g);

        satisfiable = true;
        for (int i = 0; i < var.size(); i++) {
            if (scc[i * 2] == scc[i * 2 + 1]) {
                satisfiable = false;
            }
            var[i] = scc[i * 2] > scc[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