結果
問題 | No.470 Inverse S+T Problem |
ユーザー | tubo28 |
提出日時 | 2016-12-20 13:50:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,584 bytes |
コンパイル時間 | 2,049 ms |
コンパイル使用メモリ | 181,564 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-12-22 13:34:14 |
合計ジャッジ時間 | 3,243 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | WA | - |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 9 ms
6,656 KB |
testcase_07 | AC | 8 ms
6,656 KB |
testcase_08 | AC | 8 ms
6,656 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 3 ms
5,248 KB |
testcase_29 | AC | 69 ms
8,192 KB |
testcase_30 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(c) begin(c), end(c) #define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl using Weight = int; using Capacity = int; struct Edge { int src, dst; Weight weight; Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {} }; using Edges = vector<Edge>; using Graph = vector<Edges>; using Array = vector<Weight>; using Matrix = vector<Array>; vector<int> tarjanScc(const Graph &g){ int n = g.size(), idx = 0, k = 0, s = 0; vector<int> index(n, -1), lowlink(n), onStack(n), cmp(n), stk(n); function<void(int)> strongconnect; strongconnect = [&](int v){ index[v] = lowlink[v] = idx++; stk[s++] = v; onStack[v] = true; for(auto &e : g[v]){ int w = e.dst; if(index[w] == -1){ strongconnect(w); lowlink[v] = min(lowlink[v], lowlink[w]); } else if(onStack[w]){ lowlink[v] = min(lowlink[v], index[w]); } } if(lowlink[v] == index[v]){ int w; do { w = stk[--s]; onStack[w] = false; cmp[w] = k; } while(w != v); ++k; } }; for(int v = 0; v < n; v++) if(index[v] == -1) strongconnect(v); return cmp; }; int main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector<string> ss(n); rep(i, n) cin >> ss[i]; if(n > 2756){ cout << "Impossible" << endl; exit(0); } int nn = n+n; Graph g(nn); auto sep = [&](int u, int v){ int iu = (u+n) % nn; int iv = (v+n) % nn; g[u].emplace_back(u, v, 1); g[iv].emplace_back(iv, iu, 1); }; vector<string> a(n), ab(n), bc(n), c(n); rep(i, n){ string &s = ss[i]; a[i] = s.substr(0, 1); ab[i] = s.substr(0, 2); bc[i] = s.substr(1); c[i] = s.substr(2); } rep(i, n) rep(j, i){ if(a[i] == a[j] || bc[i] == bc[j]) sep(i, j+n); if(a[i] == c[j] || bc[i] == ab[j]) sep(i, j); if(c[i] == a[j] || ab[i] == bc[j]) sep(i+n, j+n); if(c[i] == c[j] || ab[i] == ab[j]) sep(i+n, j); } vector<int> cmp = tarjanScc(g); rep(i, n){ if(cmp[i] == cmp[i+n]){ cout << "Impossible" << '\n'; exit(0); } } rep(i, n){ if(cmp[i] < cmp[i+n]) cout << ab[i] << ' ' << c[i] << '\n'; else cout << a[i] << ' ' << bc[i] << '\n'; } }