:warning: test/Tree/doubling/typical90-bf.test.cpp

Depends on

Code 

// competitive-verifier: PROBLEM https://atcoder.jp/contests/typical90/tasks/typical90_bf
// competitive-verifier: IGNORE
// testcase id is different from url

#include "Tree/doubling.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long N, K;
    cin >> N >> K;

    Doubling graph(100000, K);

    for (int x = 0; x < 100000; x++)
    {
        long long y = 0;
        string S = to_string(x);
        for (auto c : S)
        {
            y += c - '0';
        }

        long long z = (x + y) % 100000;
        graph.add_edge(x, z, 0);
    }

    cout << graph.step_forward(N, K).first << endl;

    return 0;
}
#line 1 "test/Tree/doubling/typical90-bf.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/typical90/tasks/typical90_bf
// competitive-verifier: IGNORE
// testcase id is different from url

#line 1 "Tree/doubling.hpp"
#include <bits/stdc++.h>
using namespace std;

template <typename T = long long>
class Doubling
{
    int N, L;

    vector<pair<int, T>> nexts;
    vector<vector<pair<int, T>>> parents;
    bool done_initialized = false;

public:
    Doubling() {};

    Doubling(int N, unsigned long long max_k) : N(N)
    {
        L = max<int>(bit_width(max_k), 1);
        nexts = vector<pair<int, T>>(N, {-1, 0});
        parents = vector<vector<pair<int, T>>>(N + 1, vector<pair<int, T>>(L, {-1, 0}));
    }

    void add_edge(int from, int to, T cost)
    {
        if (nexts[from].first != -1)
        {
            assert(false);
        }

        nexts[from] = pair(to, cost);
    }

    void init()
    {
        for (int i = 0; i < N; i++)
        {
            parents[i][0] = nexts[i];
        }

        for (int i = 0; i < L - 1; i++)
        {
            for (int v = 0; v < N; v++)
            {
                auto p1 = parents[v][i];
                auto p2 = parents[p1.first][i];
                parents[v][i + 1] = pair(p2.first, p1.second + p2.second);
            }
        }

        done_initialized = true;
    }

    // vを始点にK回移動した先のノードを返します
    pair<int, T> step_forward(int v, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            sum_cost += parents[v][bit_i].second, v = parents[v][bit_i].first;
            k ^= 1ll << bit_i;
        }

        return pair(v, sum_cost);
    }

    vector<pair<int, T>> step_forwards(const vector<int> &indeces, unsigned long long k)
    {
        if (!done_initialized)
        {
            init();
        }

        vector<pair<int, T>> result(indeces.size());
        for (int i = 0; i < indeces.size(); i++)
        {
            result[i].first = indeces[i];
        }

        T sum_cost = 0;
        while (k != 0)
        {
            int bit_i = countr_zero(k);
            for (pair<int, T> &p : result)
            {
                p.second += parents[p.first][bit_i].second, p.first = parents[p.first][bit_i].first;
            }
            k ^= 1ll << bit_i;
        }

        return result;
    }

    vector<pair<int, T>> step_forwards(unsigned long long k)
    {
        vector<int> indeces;
        for (int i = 0; i < N; i++)
        {
            indeces.push_back(i);
        }

        return step_forwards(indeces, k);
    }
};
#line 7 "test/Tree/doubling/typical90-bf.test.cpp"

using namespace std;

int main()
{
    long long N, K;
    cin >> N >> K;

    Doubling graph(100000, K);

    for (int x = 0; x < 100000; x++)
    {
        long long y = 0;
        string S = to_string(x);
        for (auto c : S)
        {
            y += c - '0';
        }

        long long z = (x + y) % 100000;
        graph.add_edge(x, z, 0);
    }

    cout << graph.step_forward(N, K).first << endl;

    return 0;
}
Back to top page