Language: C++


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

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>*> foundGroups;
        for (auto& group : groups)
        {
            if ((group.find(to) == group.end())
                && (group.find(i) == group.end()))
                continue;

            group.insert(to);
            group.insert(i);
            foundGroups.push_back(&group);
        }
        if (foundGroups.size() >= 2)
        {
            auto itr = foundGroups.begin();
            auto front = *itr;
            while (itr != foundGroups.end())
            {
                ++itr;
                foundGroups.front()->merge(**itr);
                groups.remove(**itr);
            }

            continue;
        }
        if (foundGroups.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;
    //}

    return (p.size() - 1)/* N */ - groups.size();
}

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)
{
    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;
}




TEST(AtCoder, minimumPath)
{
    EXPECT_EQ(2, minimumPath({ 0, 2, 1, 4, 3 }));
}


TEST(AtCoder, Sequence)
{
    StartSequnce startSequenc;
    {
        Sequence s(3, 1, startSequenc);
        EXPECT_EQ(2, s.current());
        s.next();
        EXPECT_EQ(3, s.current());
        s.next();
        EXPECT_EQ(2, s.current());
        s.next();
        EXPECT_EQ(3, s.current());
    }
    {
        Sequence s(5, 2, startSequenc);
        EXPECT_EQ(1, s.current());
        s.next();
        EXPECT_EQ(3, s.current());
        s.next();
        EXPECT_EQ(4, s.current());
        s.next();
        EXPECT_EQ(5, s.current());
        s.next();
        EXPECT_EQ(1, s.current());
    }
}

TEST(AtCoder, FixSequence)
{
    StartSequnce startSequenc;
    FixSequence s(2, startSequenc);
    EXPECT_EQ(2, s.current());
    s.next();
    EXPECT_EQ(2, s.current());
}


///
/// test
///
//
TEST(AtCoder, d1)
{
    std::ifstream in("testdata_d1.txt");
    testing::internal::CaptureStdout();

    d(in);

    const std::string actual = testing::internal::GetCapturedStdout();
    EXPECT_EQ(actual, "8");
}

TEST(AtCoder, d2)
{
    std::ifstream in("testdata_d2.txt");
    testing::internal::CaptureStdout();

    d(in);

    const std::string actual = testing::internal::GetCapturedStdout();
    EXPECT_EQ(actual, "1");

}

TEST(AtCoder, d3)
{
    std::ifstream in("testdata_d3.txt");
    testing::internal::CaptureStdout();

    d(in);

    const std::string actual = testing::internal::GetCapturedStdout();
    EXPECT_EQ(actual, "527841");
}

TEST(AtCoder, d4)
{
    std::ifstream in("testdata_d4.txt");
    testing::internal::CaptureStdout();

    d(in);

    const std::string actual = testing::internal::GetCapturedStdout();
    EXPECT_EQ(actual, "240");
}



Compiler output:
a.cc: In function 'void d(std::istream&)':
a.cc:151:22: error: 'unique_ptr' is not a member of 'std'
  151 |     std::vector<std::unique_ptr<ISequence>> P;
      |                      ^~~~~~~~~~
a.cc:9:1: note: 'std::unique_ptr' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
    8 | #include <cassert>
  +++ |+#include <memory>
    9 | 
a.cc:151:33: error: template argument 1 is invalid
  151 |     std::vector<std::unique_ptr<ISequence>> P;
      |                                 ^~~~~~~~~
a.cc:151:33: error: template argument 2 is invalid
a.cc:151:42: error: expected unqualified-id before '>' token
  151 |     std::vector<std::unique_ptr<ISequence>> P;
      |                                          ^~
a.cc:152:5: error: 'P' was not declared in this scope
  152 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |     ^
a.cc:152:22: error: 'make_unique' is not a member of 'std'
  152 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                      ^~~~~~~~~~~
a.cc:152:22: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:152:46: error: expected primary-expression before '>' token
  152 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                                              ^
a.cc:152:48: error: expected primary-expression before ')' token
  152 |     P.push_back(std::make_unique<StartSequnce>()); // dummy
      |                                                ^
a.cc:160:30: error: 'make_unique' is not a member of 'std'
  160 |             P.push_back(std::make_unique<Sequence>(N, i, *P.back()));
      |                              ^~~~~~~~~~~
a.cc:160:30: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:160:50: error: expected primary-expression before '>' token
  160 |             P.push_back(std::make_unique<Sequence>(N, i, *P.back()));
      |                                                  ^
a.cc:165:30: error: 'make_unique' is not a member of 'std'
  165 |             P.push_back(std::make_unique<FixSequence>(pi, *P.back()));
      |                              ^~~~~~~~~~~
a.cc:165:30: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
a.cc:165:53: error: expected primary-expression before '>' token
  165 |             P.push_back(std::make_unique<FixSequence>(pi, *P.back()));
      |                                                     ^
a.cc:168:41: error: 'pow' was not declared in this scope
  168 |     sequenceCount = static_cast<size_t>(pow(N - 1L, sequenceCount));
      |                                         ^~~
a.cc: At global scope:
a.cc:195:5: error: expected constructor, destructor, or type conversion before '(' token
  195 | TEST(AtCoder, minimumPath)
      |     ^
a.cc:201:5: error: expected constructor, destructor, or type conversion before '(' token
  201 | TEST(AtCoder, Sequence)
      |     ^
a.cc:228:5: error: expected constructor, destructor, or type conversion before '(' token
  228 | TEST(AtCoder, FixSequence)
      |     ^
a.cc:242:5: error: expected constructor, destructor, or type conversion before '(' token
  242 | TEST(AtCoder, d1)
      |     ^
a.cc:253:5: error: expected constructor, destructor, or type conversion before '(' token
  253 | TEST(AtCoder, d2)
      |     ^
a.cc:265:5: error: expected constructor, destructor, or type conversion before '(' token
  265 | TEST(AtCoder, d3)
      |     ^
a.cc:276:5: error: expected constructor, destructor, or type conversion before '(' token
  276 | TEST(AtCoder, d4)
      |     ^