제출 #253053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253053		Kubin	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	1 ms	384 KiB

garden

#include <cstdint>
#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] = u;
        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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31