結果

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

ソースコード

diff # 

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

int n;
vector<vector<int>> R;     // 隣接リスト（1-indexed）
vector<int> visited;       // 訪問済みフラグ

// DFS を行い、部分文字列（各枝の名前表現）を deque<string> として返す関数
deque<string> dfs(int x) {
    deque<string> dq;
    dq.push_back("methyl");
    visited[x] = 1;
    
    // x に接続している各頂点（置換基）について処理
    for (int nb : R[x]) {
        if (!visited[nb]) {
            dq.push_front(")");            // 現在の文字列の左端に ")" を追加
            deque<string> childStr = dfs(nb); // 再帰呼び出しで子の文字列を取得
            // 子の文字列の末尾に現在の dq の内容を連結する
            for (const auto &s : dq) {
                childStr.push_back(s);
            }
            dq = move(childStr);
            dq.push_front("(");            // 連結後、先頭に "(" を追加
        }
    }
    return dq;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    // n == 1 の場合は "methane" を出力して終了
    if(n == 1){
        cout << "methane";
        return 0;
    }
    
    // 1-indexed で扱うために n+1 要素の配列を用意
    R.assign(n+1, vector<int>());
    visited.assign(n+1, 0);
    
    // n の後の改行を読み捨てる
    string dummy;
    getline(cin, dummy);
    
    // 各頂点についての入力行を読み込む
    for (int i = 1; i <= n; i++){
        string line;
        getline(cin, line);
        istringstream iss(line);
        string token;
        while(iss >> token) {
            // "H"（水素）は無視し、それ以外は整数に変換して辺を張る
            if(token != "H") {
                int j = stoi(token);
                R[i].push_back(j);
                R[j].push_back(i);
            }
        }
    }
    
    // 重複する要素があれば除去する
    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(1) で生成された文字列の最後の要素を削除し、"methane" を末尾に追加
    ans.pop_back();
    ans.push_back("methane");
    
    // deque 内の文字列を連結して出力
    for(const auto &s: ans)
        cout << s;
    
    return 0;
}
0