oj.uz

Submission #253069

# Submission time Handle Problem Language Result Execution time Memory
253069 2020-07-26T20:21:31 Z Kubin Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 18744 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 182 ms 4368 KB Output is correct
12 Correct 326 ms 6776 KB Output is correct
13 Execution timed out 5069 ms 18744 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 182 ms 4368 KB Output is correct
12 Correct 326 ms 6776 KB Output is correct
13 Execution timed out 5069 ms 18744 KB Time limit exceeded
14 Halted 0 ms 0 KB -