結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー vjudge1
提出日時 2026-06-19 10:29:22
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,422 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,378 ms
コンパイル使用メモリ 192,340 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2026-06-19 10:29:29
合計ジャッジ時間 3,095 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 12 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int fa[MAXN * 2];
unordered_map<string, int> idMap;
int idCounter = 0;
pair<string, string> ans[MAXN];
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
int getID(const string& s) {
    if (!idMap.count(s)) {
        idMap[s] = idCounter++;
    }
    return idMap[s];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
    }
    bool impossible = false;
    for (int i = 0; i < n; i++) {
        string u;
        cin >> u;
        string s1 = u.substr(0, 1);
        string s2 = u.substr(1, 2);
        string s3 = u.substr(0, 2);
        string s4 = u.substr(2, 1);
        int id1 = getID(s1);
        int id2 = getID(s2);
        int id3 = getID(s3);
        int id4 = getID(s4);
        if (find(id1) != find(id2)) {
            fa[find(id1)] = find(id2);
            ans[i] = {s1, s2};
            continue;
        }
        if (find(id3) != find(id4)) {
            fa[find(id3)] = find(id4);
            ans[i] = {s3, s4};
            continue;
        }
        impossible = true;
        break;
    }
    if (impossible) {
        cout << "Impossible\n";
    } else {
        for (int i = 0; i < n; i++) {
            cout << ans[i].first << " " << ans[i].second << '\n';
        }
    }
    return 0;
}
0