제출 #1296425

#제출 시각아이디문제언어결과실행 시간메모리
1296425HiepVu217Vlak (COCI20_vlak)C++20
70 / 70
13 ms10672 KiB
//Proud of You//
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 2e5 + 17;
int n, m, sz, trie[N][27];
bool f[N], ex[N][7];
inline void add (string &s, bool t)
{
    int pos = 0;
    for (char c: s)
    {
        int i = c - 'a';
        if (!trie[pos][i])
        {
            trie[pos][i] = ++sz;
        }
        pos = trie[pos][i], ex[pos][t] = 1;
    }
}
inline void dfs (int u, bool t)
{
    int c0 = 0, c1 = 0;
    for (int i = 0; i < 26; ++i)
    {
        int v = trie[u][i];
        if (v)
        {
            dfs (v, t ^ 1);
            c0 += (!f[v]), c1 += f[v];
        }
    }
    if (!c0 && !c1)
    {
        if (ex[u][0] && ex[u][1])
        {
            f[u] = t ^ 1;
        }
        else
        {
            f[u] = (ex[u][0] ? 0 : 1);
        }
        return;
    }
    if (t)
    {
        f[u] = (c1 ? 1 : 0);
    }
    else
    {
        f[u] = (c0 ? 0 : 1);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        add (s, 0);
    }
    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        string s;
        cin >> s;
        add (s, 1);
    }
    dfs (0, 0);
    cout << (f[0] ? "Emilija" : "Nina");
}
#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...