Trace（経路復元）
(marathon/trace.cpp)

• View this file on GitHub
• Last update: 2025-10-19 18:25:59+09:00

• add(value, id)
  • 採用した値 value と直前の状態の識別子 id を与えて、状態を追加する
  • 追加した状態の識別子が返ってくる
• get(id)
  • 状態の識別子 id を与えると、初期状態からここに至るまでの経路を復元したものが返ってくる

Verified with

• verifying_test/AOJ/1227/trace.test.cpp

Code

template <typename Tp>
class Trace {
public:
    Trace() = default;

    int add(const Tp& value, int parent) {
        log_.emplace_back(value, parent);
        return (int)log_.size() - 1;
    }

    vector<Tp> get(int index) const {
        vector<Tp> result;
        while (index >= 0) {
            result.emplace_back(log_[index].first);
            index = log_[index].second;
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    vector<pair<Tp, int>> log_;
};

#line 1 "marathon/trace.cpp"
template <typename Tp>
class Trace {
public:
    Trace() = default;

    int add(const Tp& value, int parent) {
        log_.emplace_back(value, parent);
        return (int)log_.size() - 1;
    }

    vector<Tp> get(int index) const {
        vector<Tp> result;
        while (index >= 0) {
            result.emplace_back(log_[index].first);
            index = log_[index].second;
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    vector<pair<Tp, int>> log_;
};

Back to top page