제출 #1338860

#제출 시각아이디문제언어결과실행 시간메모리
1338860liiiiiilongVlak (COCI20_vlak)C++20
70 / 70
15 ms11076 KiB
#include <bits/stdc++.h>
#define IOS                               \
    {                                     \
        std::ios::sync_with_stdio(false); \
        std::cin.tie(0);                  \
        std::cout.tie(0);                 \
    }
#define endl '\n'
// #define vecotr vector
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using namespace std;
const i64 mod = 1e9 + 7;
const i64 INF = INT32_MAX;
struct node
{
    int nex[26], f1 = 0, f2 = 0;
};
void solve()
{
    int n;
    cin >> n;
    vector<node> tr;
    tr.reserve(1000006);
    tr.emplace_back();
    for (int i = 0; i < n; i++)
    {
        string g;
        cin >> g;
        int cr = 0;
        for (int j = 0; j < g.size(); j++)
        {
            if (tr[cr].nex[g[j] - 'a'] == 0)
            {
                tr[cr].nex[g[j] - 'a'] = tr.size();
                tr.emplace_back();
            }
            cr = tr[cr].nex[g[j] - 'a'];
            tr[cr].f1 = 1;
        }
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string g;
        cin >> g;
        int cr = 0;
        for (int j = 0; j < g.size(); j++)
        {
            if (tr[cr].nex[g[j] - 'a'] == 0)
            {
                tr[cr].nex[g[j] - 'a'] = tr.size();
                tr.emplace_back();
            }
            cr = tr[cr].nex[g[j] - 'a'];
            tr[cr].f2 = 1;
        }
    }
    vector<int> win(tr.size() + 1);
    vector<int> lose(tr.size() + 1);
    auto dfs = [&](auto self, int cr) -> void
    {
        int f = 0;
        for (int i = 0; i < 26; i++)
        {
            int to = tr[cr].nex[i];
            if (!to)
                continue;
            f = 1;
            self(self, to);
            if (tr[to].f1 && !lose[to])
            {
                win[cr] = 1;
            }
            if (tr[to].f2 && !win[to])
            {
                lose[cr] = 1;
            }
        }
        if (!f)
        {
            win[cr] = 0;
            lose[cr] = 0;
        }
    };
    dfs(dfs, 0);
    if (win[0])
    {
        cout << "Nina" << endl;
    }
    else
    {
        cout << "Emilija" << endl;
    }
}
int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...