Submission #253069

#	Time	Username	Problem	Language	Result	Execution time	Memory
253069		Kubin	Tropical Garden (IOI11_garden)	C++17	49 / 100	5069 ms	18744 KiB

garden

#include <functional>
#include <cstdint>
#include <cassert>
#include <vector>
#include <array>

using namespace std;

const size_t nil = SIZE_MAX;

void answer(int);

void count_routes(int _n, int _m, int _t, int E[][2], int _q, int K[])
{
    const size_t n = _n, m = _m, target = _t, q = _q;

    // get edges
    vector<array<size_t, 2>> to(n, {nil, nil});
    for(size_t i = 0; i < m; i++)
    {
        size_t u = E[i][0], v = E[i][1];
        if(to[u][0] == nil)
            to[u][0] = v;
        else if(to[u][1] == nil)
            to[u][1] = v;
        if(to[v][0] == nil)
            to[v][0] = u;
        else if(to[v][1] == nil)
            to[v][1] = u;
    }

    vector<size_t> F(2*n, nil);
    // vertex i+n is vertex after coming through best edge of vertex i
    auto nfix = [&](size_t v, size_t u) {
        return v + (to[v][0] == u ? n : 0);
    };
    for(size_t u = 0; u < n; u++)
    {
        F[u] = nfix(to[u][0], u);
        F[u+n] = nfix(to[u][1] == nil ? to[u][0] : to[u][1], u);
    }

    // rho computation
    vector<bool> vis(2*n), on(2*n);
    vector<size_t> st; st.reserve(2*n);

    vector<size_t> top(2*n, nil);
    vector<int> lambda(2*n), omega(2*n);

    vector<vector<size_t>> G(2*n);

    for(size_t s = 0; s < 2*n; s++)
    {
        G[F[s]].push_back(s);
        if(vis[s])
            continue;

        assert(st.empty());
        size_t u = s;
        while(true)
        {
            vis[u] = on[u] = true;
            st.push_back(u);

            if(on[F[u]])
            {
                vector<size_t> cycle;
                while(true)
                {
                    auto v = st.back(); st.pop_back();
                    on[v] = false;
                    cycle.push_back(v);
                    if(v == F[u])
                        break;
                }
                for(auto v : cycle)
                    omega[v] = cycle.size(), top[v] = v;
            }
            else if(vis[F[u]])
            {
                lambda[u] = lambda[F[u]] + 1;
                top[u] = top[F[u]];
            }
            else
                { u = F[u]; continue; }
            break;
        }
        while(not st.empty())
        {
            auto v = st.back(); st.pop_back();
            lambda[v] = lambda[F[v]] + 1;
            top[v] = top[F[v]];
            on[v] = false;
        }
    }


    // queries

    function<pair<vector<int>, bool>(size_t)> get_tab = [&](size_t t) -> pair<vector<int>, bool> {
        if(lambda[t])
        {
            vector<int> cnt;
            function<void(size_t, size_t)> dfs = [&](size_t u, size_t d) {
                while(cnt.size() <= d) cnt.push_back(0);
                cnt[d]++;
                for(auto v : G[u])
                    dfs(v, d + 1);
            };
            dfs(t, 0);
            return {cnt, false};
        }
        else
        {
            size_t u = t;
            vector<int> cnt(omega[t], 1);
            for(int i = 0; i < omega[t]; i++, u = F[u])
            {
                int sh = i ? omega[t] - i : 0;
                for(auto v : G[u])
                  if(lambda[v])
                {
                    auto [sub, _] = get_tab(v);
                    (void)_;
                    for(size_t d = 0; d < sub.size(); d++)
                        cnt[(sh + d) % omega[t]] += sub[d];
                }
            }
            return {cnt, true};
        }
    };

    auto count = [&](int k, size_t t) {
        auto T = get_tab(t);

        int result = 0;
        for(size_t u = 0; u < n; u++)
        {
            size_t v = u;
            int l = k;
            while(l)
            {
                if(not lambda[v] and l >= omega[v])
                    l %= omega[v];
                else if(lambda[v] and l >= lambda[v])
                    l -= lambda[v], v = top[v];
                else
                    v = F[v], l--;
            }
            if(v == t)
                result++;
        }
        return result;
    };

    for(size_t que = 0; que < q; que++)
    {
        int k = K[que];
        answer(count(k, target) + count(k, target + n));
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31