結果

問題 No.2820 Non-Preferred IUPAC Nomenclature
ユーザー D M
提出日時 2025-02-12 10:43:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,846 bytes
コンパイル時間 1,807 ms
コンパイル使用メモリ 121,904 KB
実行使用メモリ 118,740 KB
最終ジャッジ日時 2025-02-12 10:43:19
合計ジャッジ時間 14,430 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <deque>
#include <algorithm>
using namespace std;

int n;                                // 頂点数
vector<vector<int>> R;                // グラフの隣接リスト（1-indexed）
vector<int> visited;                  // 探索済みフラグ（1-indexed）

// DFS 関数：頂点 x から探索し、化学構造を表す文字列（deque<string>）を返す
deque<string> dfs(int x) {
    deque<string> dq;
    // 現在の頂点 x に対して "methyl" を末尾に追加
    dq.push_back("methyl");
    visited[x] = 1;
    
    // x の隣接頂点を順に探索
    for (int nxt : R[x]) {
        if (!visited[nxt]) {
            // 未訪問の頂点の場合、まず直前に ")" を先頭に追加
            dq.push_front(")");
            // 再帰的に隣接頂点を探索
            deque<string> sub = dfs(nxt);
            // 返ってきた deque の末尾に現在の dq の内容を連結する
            for (const string &s : dq) {
                sub.push_back(s);
            }
            // 連結後の deque を dq に更新
            dq = move(sub);
            // 探索が終わった枝を "(" で囲むため、先頭に "(" を追加
            dq.push_front("(");
        }
    }
    return dq;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 入力：頂点数の読み込み
    cin >> n;
    cin.ignore();  // 改行を読み捨てる

    // グラフと探索フラグの初期化（頂点は 1-indexed とする）
    R.resize(n + 1);
    visited.assign(n + 1, 0);

    // 各頂点について、隣接頂点の情報を入力する
    // 各行には "H" か頂点番号が空白区切りで与えられる
    for (int i = 1; i <= n; i++){
        string line;
        getline(cin, line);
        istringstream iss(line);
        string token;
        while (iss >> token) {
            if (token != "H") {
                int j = stoi(token);
                // 双方向にエッジを張る
                R[i].push_back(j);
                R[j].push_back(i);
            }
        }
    }
    
    // 重複する隣接頂点を削除（Python の list(set(...)) と同等）
    for (int i = 0; i <= n; i++){
        sort(R[i].begin(), R[i].end());
        R[i].erase(unique(R[i].begin(), R[i].end()), R[i].end());
    }
    
    // DFS を開始（根は頂点 1）
    deque<string> ans = dfs(1);
    // DFS から返ってきた deque の最後の要素を削除
    if (!ans.empty()) {
        ans.pop_back();
    }
    // 末尾に "methane" を追加
    ans.push_back("methane");
    
    // deque の内容を連結して出力
    string output;
    for (const string &s : ans) {
        output += s;
    }
    cout << output << "\n";
    
    return 0;
}
0