oj.uz

Submission #253063

# Submission time Handle Problem Language Result Execution time Memory
253063 2020-07-26T20:02:06 Z Kubin Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 2048 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;

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

    for(size_t s = 0; s < 2*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;
            }
            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
    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
49.0 / 49.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Execution timed out 5054 ms 2048 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Execution timed out 5054 ms 2048 KB Time limit exceeded
12 Halted 0 ms 0 KB -