結果

問題 No.470 Inverse S+T Problem
ユーザー yuppe19 😺yuppe19 😺
提出日時 2016-12-26 00:03:16
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,720 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 53,288 KB
最終ジャッジ日時 2023-08-24 01:25:46
合計ジャッジ時間 894 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:9:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<vector<int>> fG, rG;
   ^~~~~~
   perror
main.cpp:10:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<bool> used;
   ^~~~~~
   perror
main.cpp:11:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<int> order; // 属する強連結成分のトポロジカル順序
   ^~~~~~
   perror
main.cpp:12:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<int> vertices; // 帰りがけ順の並び
   ^~~~~~
   perror
main.cpp:19:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<int> get_order();
   ^~~~~~
   perror
main.cpp:20:3: error: ‘vector’ does not name a type; did you mean ‘perror’?
   vector<vector<int>> restore_sccs(); // solve() の後に呼び出して強連結成分をトポロジカル順序で返す
   ^~~~~~
   perror
main.cpp: In constructor ‘SCC::SCC(int)’:
main.cpp:24:3: error: ‘fG’ was not declared in this scope
   fG.assign(n, vector<int>());
   ^~
main.cpp:24:16: error: ‘vector’ was not declared in this scope
   fG.assign(n, vector<int>());
                ^~~~~~
main.cpp:24:16: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:3:1:
+#include <vector>
 using namespace std;
main.cpp:24:16:
   fG.assign(n, vector<int>());
                ^~~~~~
main.cpp:24:23: error: expected primary-expression before ‘int’
   fG.assign(n, vector<int>());
                       ^~~
main.cpp:25:3: error: ‘rG’ was not declared in this scope
   rG.assign(n, vector<int>());
   ^~
main.cpp:25:23: error: expected primary-expression before ‘int’
   rG.assign(n, vector<int>());
                       ^~~
main.cpp: In member function ‘void SCC::add_edge(int, int)’:
main.cpp:29:3: error: ‘fG’ was not declared in this scope
   fG[u].push_back(v);
   ^~
main.cpp:30:3: e

ソースコード

diff # 

#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;
}
0