455B

Tutorial

Trie can be implemented with a two dimentional array.

Solution

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define D(x) x

const int MAX_CHAR_NUM = 30;
const int MAX_N = int(1e5) + 10;
const int MAX_NODE_NUM = MAX_N;

int trie[MAX_NODE_NUM][MAX_CHAR_NUM];
int node_num;

int n, round_num;
char st[MAX_N];
bool leaf;

void trie_init()
{
    memset(trie, -1, sizeof(trie));
    node_num = 1;
}

int convert(char ch)
{
    return ch - 'a';
}

void add(char* st)
{
    int u = 0;
    for (int i = 0; st[i]; i++)
    {
        int index = convert(st[i]);
        if (trie[u][index] == -1)
        {
            trie[u][index] = node_num++;
        }
        u = trie[u][index];
    }
}

void input()
{
    scanf("%d%d", &n, &round_num);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", st);
        add(st);
    }
}

bool dfs(int u)
{
    bool have_child = false;
    bool ret = false;
    for (int i = 0; i < 26; i++)
    {
        if (trie[u][i] != -1)
        {
            have_child = true;
            ret = ret || !dfs(trie[u][i]);
        }
    }
    if (have_child)
        return ret;
    return leaf;
}

void output()
{
    for (int i = 0; i < 24; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            printf("%d ", trie[i][j]);
        }
        puts("");
    }
}

int main()
{
    trie_init();
    input();
    leaf = false;
    bool win = dfs(0);
    leaf = true;
    bool lose = dfs(0);
    if (win && lose)
    {
        puts("First");
    }else if (win && !lose)
    {
        if (round_num & 1)
            puts("First");
        else
            puts("Second");
    }else if (!win)
    {
        puts("Second");
    }
    return 0;
}