#141433 (C++11(old_compat)) No.470 Inverse S+T Problem

• 問題: No.470 Inverse S+T Problem
• ユーザー: yuppe19 😺
• 提出日時: 2016-12-26 00:03:16
• 言語: C++11(old_compat) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,720 bytes
• コンパイル時間: 2,297 ms
• コンパイル使用メモリ: 193,404 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-03-08 16:08:18
• 合計ジャッジ時間: 3,052 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 27

ソースコード

#include <iostream>
#include <algorithm>
using namespace std;

// 強連結成分分解: Strongly Connected Components
class SCC {
  int n;
  int scc_num;
  vector<vector<int>> fG, rG;
  vector<bool> used;
  vector<int> order; // 属する強連結成分のトポロジカル順序
  vector<int> vertices; // 帰りがけ順の並び
  void dfs(int u);
  void rdfs(int v, int k);
public:
  SCC(int n);
  void add_edge(int u, int v); // u から v に辺を張る
  void solve();
  vector<int> get_order();
  vector<vector<int>> restore_sccs(); // solve() の後に呼び出して強連結成分をトポロジカル順序で返す
};

SCC::SCC(int n) : n(n) {
  fG.assign(n, vector<int>());
  rG.assign(n, vector<int>());
}

void SCC::add_edge(int u, int v) {
  fG[u].push_back(v);
  rG[v].push_back(u);
}

void SCC::dfs(int u) {
  used[u] = true;
  for(int v : fG[u]) {
    if(!used[v]) { dfs(v); }
  }
  vertices.push_back(u);
}

void SCC::rdfs(int v, int k) {
  used[v] = true;
  order[v] = k;
  for(int u : rG[v]) {
    if(!used[u]) { rdfs(u, k); }
  }
}

vector<int> SCC::get_order() {
  return order;
}

void SCC::solve() {
  used.assign(n, false);
  order.assign(n, 0);
  vertices.clear();
  for(int u=0; u<n; ++u) {
    if(!used[u]) { dfs(u); }
  }
  used.assign(n, false);
  scc_num = 0;
  for(int i=vertices.size()-1; i>=0; --i) {
    if(!used[vertices[i]]) { rdfs(vertices[i], scc_num++); }
  }
}

vector<vector<int>> SCC::restore_sccs() {
  vector<vector<int>> res(scc_num, vector<int>()); // res[scc_num][]
  for(int i=0; i<n; ++i) {
    res[order[i]].push_back(i);
  }
  return res;
}

// 2-SAT
class TwoSAT {
  int n;
  SCC g;
public:
  TwoSAT(int n);
  void add_clause(bool flag0, int x0, bool flag1, int x1); // (x0 | x1)という節を追加する
  vector<bool> solve(); // 戻り値: 可能なら真偽の割り当て、不可能なら空配列
};

TwoSAT::TwoSAT(int n) : n(n), g(2*n) {}

void TwoSAT::add_clause(bool flag0, int x0, bool flag1, int x1) {
  g.add_edge(x0 + n * !flag0, x1 + n * flag1); // !x0 => x1
  g.add_edge(x1 + n * !flag1, x0 + n * flag0); // !x1 => x0
  // メモ: (x0 | x1) = (!x0 => x1 & !x1 => x0)
}

vector<bool> TwoSAT::solve() {
  g.solve();
  vector<int> order = g.get_order();
  vector<bool> res(n);
  for(int i=0; i<n; ++i) {
    if(order[i] == order[i+n]) { return vector<bool>(); } // 充足不可能
    if(order[i] > order[i+n])  { res[i] = true; }
  }
  return res;
}

int main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  int n; cin >> n;
  if(n > 60) {
    cout << "Impossible\n";
    return 0;
  }
  vector<string> u(n);
  for(int i=0; i<n; ++i) {
    cin >> u[i];
  }
  TwoSAT sat(n);
  string s1, s2, t1, t2;
  for(int i=0; i<n; ++i) {
    string s = u[i];
    for(int j=i+1; j<n; ++j) {
      string t = u[j];
      // "一文字, 二文字" は false, "二文字, 一文字" は true
      s1 = s.substr(0, 1); s2 = s.substr(1);    t1 = t.substr(0, 1); t2 = t.substr(1);    if(s1 == t1 || s2 == t2) { sat.add_clause(false, i, false, j); }
      s1 = s.substr(0, 1); s2 = s.substr(1);    t1 = t.substr(2);    t2 = t.substr(0, 2); if(s1 == t1 || s2 == t2) { sat.add_clause(false, i, true,  j); }
      s1 = s.substr(2);    s2 = s.substr(0, 2); t1 = t.substr(0, 1); t2 = t.substr(1);    if(s1 == t1 || s2 == t2) { sat.add_clause(true,  i, false, j); }
      s1 = s.substr(2);    s2 = s.substr(0, 2); t1 = t.substr(2);    t2 = t.substr(0, 2); if(s1 == t1 || s2 == t2) { sat.add_clause(true,  i, true,  j); }
    }
  }
  vector<bool> res = sat.solve();
  if(!res.size()) {
    cout << "Impossible\n";
    return 0;
  }
  for(int i=0; i<n; ++i) {
    int p = 1 + res[i];
    cout << u[i].substr(0, p) << " " << u[i].substr(p) << '\n';
  }
  return 0;
}