Submission #1296425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296425		HiepVu217	Vlak (COCI20_vlak)	C++20	70 / 70	13 ms	10672 KiB

Main

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10