Submission #253058

#	Time	Username	Problem	Language	Result	Execution time	Memory
253058		Kubin	Tropical Garden (IOI11_garden)	C++17	49 / 100	5039 ms	1408 KiB

garden

#include <cstdint>
#include <vector>
#include <array>
#include <iostream>

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

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

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

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