結果

問題 No.470 Inverse S+T Problem
ユーザー pekempeypekempey
提出日時 2016-12-20 00:55:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,658 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 197,776 KB
実行使用メモリ 16,224 KB
最終ジャッジ日時 2023-08-24 01:04:31
合計ジャッジ時間 4,563 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 WA -
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 104 ms
16,160 KB
testcase_07 AC 106 ms
16,224 KB
testcase_08 AC 101 ms
16,180 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 WA -
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 18 ms
6,240 KB
testcase_29 AC 5 ms
4,440 KB
testcase_30 AC 12 ms
5,712 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;

    map<string, vector<int>> mp0; // *ab
    map<string, vector<int>> mp1; // a*b
    map<string, vector<int>> mp2; // ab*
    vector<string> s(n);
    SAT2 sat(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        mp0[s[i].substr(1, 2)].push_back(i);
        mp1[s[i].substr(0, 1) + s[i].substr(2, 1)].push_back(i);
        mp2[s[i].substr(0, 2)].push_back(i);
    }

    for (auto &mp : { mp0, mp1, mp2 }) {
        for (auto kv : mp) {
            if (kv.second.size() >= 3) {
                puts("Impossible");
                return 0;
            }
            auto &v = kv.second;
            for (int i = 0; i < v.size(); i++) {
                for (int j = i + 1; j < v.size(); j++) {
                    string a = s[v[i]];
                    string b = s[v[j]];

                    if (a.substr(0, 1) == b.substr(0, 1) || a.substr(1, 2) == b.substr(1, 2)) {
                        sat.add(v[i], true, v[j], true);
                    }
                    if (a.substr(0, 1) == b.substr(2, 1) || a.substr(1, 2) == b.substr(0, 2)) {
                        sat.add(v[i], true, v[j], false);
                    }
                    if (a.substr(0, 2) == b.substr(1, 2) || a.substr(2, 1) == b.substr(0, 1)) {
                        sat.add(v[i], false, v[j], true);
                    }
                    if (a.substr(0, 2) == b.substr(0, 2) || a.substr(2, 1) == b.substr(2, 1)) {
                        sat.add(v[i], false, v[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