結果

問題 No.470 Inverse S+T Problem
ユーザー mamekin
提出日時 2017-06-11 14:37:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 4,094 bytes
コンパイル時間 1,882 ms
コンパイル使用メモリ 135,448 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-22 13:43:59
合計ジャッジ時間 3,107 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

void stronglyConnectedComponents(
    const vector<vector<int> >& edges, vector<int>& indexConvert,
    vector<vector<int> >& nodesOut)
{
    const int n = edges.size();
    vector<int> num(n, -1), low(n, -1);
    vector<bool> isStk(n, false);
    stack<int> stk;
    int cnt = -1;
    nodesOut.clear();

    for(int i=0; i<n; ++i){
        stack<pair<int, unsigned> > arg;
        arg.push(make_pair(i, 0));

        while(!arg.empty()){
            int v = arg.top().first;
            unsigned j = arg.top().second;
            arg.pop();

            if(j == 0){
                if(num[v] != -1)
                    continue;
                num[v] = low[v] = ++ cnt;
                stk.push(v);
                isStk[v] = true;
            }
            else{
                int w = edges[v][j-1];
                if(isStk[w])
                    low[v] = min(low[v], low[w]);
            }

            if(j < edges[v].size()){
                arg.push(make_pair(v, j + 1));
                int w = edges[v][j];
                arg.push(make_pair(w, 0));
            }
            else if(low[v] == num[v]){
                nodesOut.push_back(vector<int>());
                for(;;){
                    int w = stk.top();
                    stk.pop();
                    isStk[w] = false;
                    nodesOut.back().push_back(w);
                    if(v == w)
                        break;
                }
            }
        }
    }

    reverse(nodesOut.begin(), nodesOut.end()); // DAGにするために反転させる
    const int m = nodesOut.size();
    indexConvert.resize(n);
    for(int i=0; i<m; ++i){
        for(unsigned j=0; j<nodesOut[i].size(); ++j)
            indexConvert[nodesOut[i][j]] = i;
    }
}

bool is2sat(int n, const vector<pair<int, bool> >& v, vector<bool>& ans)
{
    vector<vector<int> > edges(2*n);
    for(unsigned i=0; i<v.size(); i+=2){
        int a = v[i].first * 2 + (v[i].second ? 0 : 1);
        int b = v[i+1].first * 2 + (v[i+1].second ? 0 : 1);
        edges[a^1].push_back(b);
        edges[b^1].push_back(a);
    }

    vector<int> indexConvert;
    vector<vector<int> > nodes;
    stronglyConnectedComponents(edges, indexConvert, nodes);

    ans.resize(n);
    for(int i=0; i<n; ++i){
        if(indexConvert[2*i] < indexConvert[2*i+1])
            ans[i] = false;
        else if(indexConvert[2*i+1] < indexConvert[2*i])
            ans[i] = true;
        else
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    if(n > 52){
        cout << "Impossible" << endl;
        return 0;
    }

    vector<string> u(n);
    for(int i=0; i<n; ++i)
        cin >> u[i];

    vector<pair<int, bool> > v;
    for(int a=0; a<n; ++a){
        for(int b=0; b<a; ++b){
            for(int i=0; i<2; ++i){
                for(int j=0; j<2; ++j){
                    set<string> s;
                    s.insert(u[a].substr(0, i+1));
                    s.insert(u[a].substr(i+1));
                    s.insert(u[b].substr(0, j+1));
                    s.insert(u[b].substr(j+1));
                    if(s.size() < 4){
                        v.push_back(make_pair(a, i==0));
                        v.push_back(make_pair(b, j==0));
                    }
                }
            }
        }
    }

    vector<bool> ans;
    if(!is2sat(n, v, ans)){
        cout << "Impossible" << endl;
        return 0;
    }

    for(int i=0; i<n; ++i){
        if(!ans[i])
            cout << u[i].substr(0, 1) << ' ' << u[i].substr(1) << endl;
        else
            cout << u[i].substr(0, 2) << ' ' << u[i].substr(2) << endl;
    }
    return 0;
}
0