結果

問題 No.2820 Non-Preferred IUPAC Nomenclature
ユーザー Tatsu_mrTatsu_mr
提出日時 2024-07-26 22:14:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,421 bytes
コンパイル時間 2,840 ms
コンパイル使用メモリ 220,756 KB
実行使用メモリ 114,108 KB
最終ジャッジ日時 2024-07-26 22:14:48
合計ジャッジ時間 6,088 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,884 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    Edge() {}
    Edge(int from_, int to_, long long cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {}
    
    int from, to;
    long long cost;
    int idx;
};

struct Graph {
    private:
    int n, m;
    bool dir;
    vector<vector<Edge>> g;
    vector<Edge> e;
    
    public:
    Graph(int n_, bool dir_) : n(n_), m(0), dir(dir_), g(n), e(0) {}
    Graph(int n_) : n(n_), m(0), dir(false), g(n), e(0) {}
    
    int size() {
        return n;
    }
    
    int edgesize() {
        return m;
    }
    
    bool directed() {
        return dir;
    }
    
    void add(int u, int v, long long w) {
        g[u].emplace_back(u, v, w, m);
        e.emplace_back(u, v, w, m);
        if (!dir) {
            g[v].emplace_back(v, u, w, m);
        }
        m++;
    }
    
    vector<Edge> operator[](int v) {
        return g[v];
    }
    
    Edge edge(int i) {
        return e[i];
    }
};

struct Tree {
    private:
    int n;
    Graph g;
    vector<vector<int>> parent;
    vector<int> depth;
    vector<long long> distance;
    int root;
    
    void build() {
        queue<int> q;
        depth[root] = 0;
        distance[root] = 0LL;
        q.push(root);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto e : g[v]) {
                int nv = e.to;
                long long d = e.cost;
                if (depth[nv] == -1) {
                    depth[nv] = depth[v] + 1;
                    distance[nv] = distance[v] + d;
                    parent[nv][0] = v;
                    q.push(nv);
                }
            }
        }
        for (int j = 1; j < 30; j++) {
            for (int i = 0; i < n; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
    
    public:
    Tree(Graph g_) : n(g_.size()), g(g_), parent(n, vector<int>(30)), depth(n, -1), distance(n, -1LL), root(0) {
        build();
    }
    Tree(Graph g_, int root_) :n(g_.size()), g(g_), parent(n, vector<int>(30)), depth(n, -1), distance(n, -1LL), root(root_) {
        build();
    }
    
    int lca(int u, int v) {
        if (dep(u) < dep(v)) {
            swap(u, v);
        }
        u = la(u, dep(u) - dep(v));
        if (u == v) {
            return u;
        }
        for (int j = 29; j >= 0; j--) {
            if (parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        return par(u);
    }
    
    int la(int v, int k) {
        int res = v;
        for (int j = 0; j < 30; j++) {
            if (k & (1 << j)) {
                res = parent[res][j];
            }
        }
        return res;
    }
    
    int jump(int u, int v, int i) {
        int l = lca(u, v);
        int cnt = dep(u) + dep(v) - 2 * dep(l);
        if (cnt < i) {
            return -1;
        }
        if (i <= dep(u) - dep(l)) {
            return la(u, i);
        } else {
            return la(v, cnt - i);
        }
    }
    
    long long dist(int u, int v) {
        int l = lca(u, v);
        return distance[u] + distance[v] - 2 * distance[l];
    }
    
    int par(int v) {
        return parent[v][0];
    }
    
    int dep(int v) {
        return depth[v];
    }
    
    bool onpath(int u, int v, int w) {
        return dist(u, w) + dist(v, w) == dist(u, v);
    }
};

int main() {
    int n;
    cin >> n;
    Graph g(n);
    for (int u = 0; u < n; u++) {
        for (int i = 0; i < 4; i++) {
            string s;
            cin >> s;
            if (s != "H") {
                int v = stoi(s) - 1;
                if (u < v) {
                    g.add(u, v, 1LL);
                }
            }
        }
    }
    Tree tr(g);
    auto f = [&](auto f, int v) -> string {
        string res = "";
        for (auto e : g[v]) {
            int nv = e.to;
            if (tr.dep(nv) < tr.dep(v)) {
                continue;
            }
            string s = f(f, nv);
            s.back() = 'y';
            res += "(" + s + ")";
        }
        res += "x";
        return res;
    };
    string ans = f(f, 0);
    for (char c : ans) {
        if (c == ')' || c == '(') {
            cout << c;
        } else if (c == 'y') {
            cout << "methyl";
        } else {
            cout << "methane";
        }
    }
    cout << endl;
}
0