oj.uz

Submission #253059

# Submission time Handle Problem Language Result Execution time Memory
253059 2020-07-26T19:53:13 Z Kubin Tropical Garden (IOI11_garden) C++17
0 / 100
 408 ms 262148 KB 
#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;

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

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

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

    for(size_t s = 0; s < n; 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;

                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;
                }
            }
            else if(vis[F[u]])
            {
                lambda[u] = lambda[F[u]] + 1;
                top[u] = top[F[u]];
            }
        }
    }

    for(size_t que = 0; que < q; que++)
    {
        int k = K[que];

        int result = 0;
        for(size_t u = 0; u < n; u++)
        {
            size_t v = u;
            int l = k;
            while(l)
            {
                v = F[v];
                l--;
            }
            if(v == target or v == target+n)
                result++;
        }
        answer(result);
    }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Runtime error 408 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 408 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 408 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -