結果

問題 No.2820 Non-Preferred IUPAC Nomenclature
ユーザー Tatsu_mr
提出日時 2024-07-27 10:50:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 528 ms / 2,000 ms
コード長 4,203 bytes
コンパイル時間 2,286 ms
コンパイル使用メモリ 211,048 KB
最終ジャッジ日時 2025-02-23 19:03:36
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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);
    string ans = "";
    auto f = [&](auto f, int v) -> void {
        string res = "";
        for (auto e : g[v]) {
            int nv = e.to;
            if (tr.dep(nv) < tr.dep(v)) {
                continue;
            }
            ans += "(";
            f(f, nv);
            ans += "yl)";
        }
        ans += "meth";
    };
    f(f, 0);
    ans += "ane";
    cout << ans << endl;
}
0