Language: C++


#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <string>
#include <algorithm>

static size_t minimumPath(const std::vector<int>& p)
{
    std::list<std::set<int>> groups;
    for (size_t i = 1; i < p.size(); ++i)
    {
        const auto& to = p[i];
        std::list<std::set<int>*> foundGoups;
        for (auto& group : groups)
        {
            if ((group.find(to) == group.end())
                && (group.find(i) == group.end()))
                continue;

            group.insert(to);
            group.insert(i);
            foundGoups.push_back(&group);
        }
        if (foundGoups.size() == 2)
        {
            foundGoups.front()->merge(*foundGoups.back());
            groups.remove(*foundGoups.back());

            continue;
        }
        if (foundGoups.size() == 1)
            continue;

        std::set<int> newGroup;
        newGroup.insert(to);
        newGroup.insert(i);
        groups.push_back(newGroup);
    }

    size_t minimumPath = 0;
    for (const auto& group : groups)
    {
        minimumPath += group.size() - 1;
    }

    return minimumPath % 100000007;
}

class ISequence
{
public:
    ISequence() = default;
    virtual ~ISequence() = default;
    ISequence(const ISequence&) = default;
    ISequence& operator=(const ISequence&) = default;

    virtual void next() = 0;
    virtual int current() const = 0;
};

class StartSequnce final : public ISequence
{
public:
    StartSequnce() = default;
    virtual void next() override
    {
    }

    virtual int current() const override
    {
        return 0;
    }
};

class FixSequence final : public ISequence
{
public:
    FixSequence(int fix, ISequence& nextSequence)
        : fix_(fix), nextSequence_(nextSequence)
    {
    }
    virtual void next() override
    {
        nextSequence_.next();
    }

    virtual int current() const override
    {
        return fix_;
    }
private:
    const int fix_;
    ISequence& nextSequence_;
};

class Sequence final : public ISequence
{
public:
    Sequence(int N, int idx, ISequence& nextSequence)
        : current_(1), N_(N), idx_(idx), nextSequence_(nextSequence)
    {
        check();
    }

    void check()
    {
        if (current_ == idx_)
            ++current_;

        if (current_ > N_)
        {
            nextSequence_.next();
            current_ = 1;
            if (current_ == idx_)
                ++current_;
        }
    }

    virtual void next() override
    {
        ++current_;
        check();
    }

    virtual int current() const override
    {
        return current_;
    }

private:
    int current_;
    int N_;
    int idx_;
    ISequence& nextSequence_;
};

void d(std::istream& in)
{
    int N;
    in >> N;

    std::vector<std::unique_ptr<ISequence>> P;
    P.push_back(std::make_unique<StartSequnce>()); // dummy
    size_t sequenceCount = 0;
    for (int i = 1; i <= N; ++i)
    {
        int pi = 0;
        in >> pi;
        if (pi == -1)
        {
            P.push_back(std::make_unique<Sequence>(N, i, *P.back()));
            ++sequenceCount;
        }
        else
        {
            P.push_back(std::make_unique<FixSequence>(pi, *P.back()));
        }
    }
    sequenceCount = static_cast<size_t>(std::pow(N - 1L, sequenceCount));

    size_t totalMinimumPath = 0;
    for (size_t i = 0; i < sequenceCount; ++i)
    {
        std::vector<int> toList;
        for (auto& p : P)
        {
            toList.push_back(p->current());
        }
        totalMinimumPath += minimumPath(toList);
        totalMinimumPath %= 100000007;

        P.back()->next();
    }

    std::cout << totalMinimumPath;
}

int main(int, char* [])
{
    d(std::cin);
    return 0;
}


Compiler output:
a.cc: In function 'void d(std::istream&)':
a.cc:144:22: error: 'unique_ptr' is not a member of 'std'
  144 |     std::vector<std::unique_ptr<ISequence>> P;
      |                      ^~~~~~~~~~
a.cc:8:1: note: 'std::unique_ptr' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
    7 | #include <algorithm>
  +++ |+#include <memory>
    8 | 
a.cc:144:33: error: template argument 1 is invalid
  144 |     std::vector<std::unique_ptr<ISequence>> P;
      |                                 ^~~~~~~~~
a.cc:144:33: error: template argument 2 is invalid
a.cc:144:42: error: expected unqualified-id before '>' token
  144 |     std::vector<std::unique_ptr<ISequence>> P;
      |                                          ^~
a.cc:145:5: error: 'P' was not declared in this scope
  145 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |     ^
a.cc:145:22: error: 'make_unique' is not a member of 'std'
  145 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                      ^~~~~~~~~~~
a.cc:145:22: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:145:46: error: expected primary-expression before '>' token
  145 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                                              ^
a.cc:145:48: error: expected primary-expression before ')' token
  145 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                                                ^
a.cc:153:30: error: 'make_unique' is not a member of 'std'
  153 |             P.push_back(std::make_unique<Sequence>(N, i, *P.back()));
      |                              ^~~~~~~~~~~
a.cc:153:30: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:153:50: error: expected primary-expression before '>' token
  153 |             P.push_back(std::make_unique<Sequence>(N, i, *P.back()));
      |                                                  ^
a.cc:158:30: error: 'make_unique' is not a member of 'std'
  158 |             P.push_back(std::make_unique<FixSequence>(pi, *P.back()));
      |                              ^~~~~~~~~~~
a.cc:158:30: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:158:53: error: expected primary-expression before '>' token
  158 |             P.push_back(std::make_unique<FixSequence>(pi, *P.back()));
      |                                                     ^
a.cc:161:46: error: 'pow' is not a member of 'std'
  161 |     sequenceCount = static_cast<size_t>(std::pow(N - 1L, sequenceCount));
      |                                              ^~~