Language: C++


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

static size_t minimumPath(const std::vector<size_t>& p)
{
    std::list<std::set<size_t>> groups;
    for (size_t i = 1; i < p.size(); ++i)
    {
        const auto& to = p[i];
        std::list<std::set<size_t>*> 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<size_t> newGroup;
        newGroup.insert(to);
        newGroup.insert(i);
        groups.push_back(newGroup);
    }

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

    size_t aa = (p.size() - 1)/* N */ - groups.size();

    assert(aa == minimumPath);

    return minimumPath;
}

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

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

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

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

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

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

class Sequence final : public ISequence
{
public:
    Sequence(size_t N, size_t 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 size_t current() const override
    {
        return current_;
    }

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

void d(std::istream& in)
{
    assert(false);
    size_t N;
    in >> N;

    std::vector<std::unique_ptr<ISequence>> P;
    P.push_back(std::make_unique<StartSequnce>()); // dummy
    size_t sequenceCount = 0;
    for (size_t 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>(pow(N - 1L, sequenceCount));

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

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

    std::cout << totalMinimumPath % 1000000007;
}

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


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