Submission #1171172

#TimeUsernameProblemLanguageResultExecution timeMemory
1171172mousebeaverVlak (COCI20_vlak)C++20
70 / 70
19 ms22512 KiB
#define ll long long
#define subINF numeric_limits<ll>::min()/2
#define pll pair<ll, ll>
#define ppl pair<pll, ll>
#define BITS 32
#include <bits/stdc++.h>
using namespace std;

//Does the moving player (bool nina) win?
bool dfs(vector<vector<ll>>& trie, vector<bool>& nina, vector<bool>& emilija, ll node, bool ninaMoves)
{
    if(ninaMoves && !nina[node])
        return false;
    if(!ninaMoves && !emilija[node])
        return false;

    bool output = false;

    for(ll i = 0; i < 26; i++)
    {
        if(trie[node][i] != -1 && ((ninaMoves && nina[trie[node][i]]) || (!ninaMoves && emilija[trie[node][i]])))
            output |= !dfs(trie, nina, emilija, trie[node][i], !ninaMoves);
    }

    return output;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n;
    cin>>n;
    vector<vector<ll>> trie(1, vector<ll> (26, -1));
    vector<bool> nina(1, true);
    vector<bool> emilija(1, true);

    for(ll i = 0; i < n; i++)
    {
        string s;
        cin>>s;
        ll k = 0;
        for(char c : s)
        {
            int ind = (int) c - (int) 'a';
            if(trie[k][ind] == -1)
            {
                trie[k][ind] = trie.size();
                nina.push_back(false);
                emilija.push_back(false);
                trie.push_back({});
                trie.back().assign(26, -1);
            }
            k = trie[k][ind];
            nina[k] = true;
        }
    }

    ll m;
    cin>>m;

    for(ll i = 0; i < m; i++)
    {
        string s;
        cin>>s;
        ll k = 0;
        for(char c : s)
        {
            int ind = (int) c - (int) 'a';
            if(trie[k][ind] == -1)
            {
                trie[k][ind] = trie.size();
                nina.push_back(false);
                emilija.push_back(false);
                trie.push_back({});
                trie.back().assign(26, -1);
            }
            k = trie[k][ind];
            emilija[k] = true;
        }
    }    

    cout<<(dfs(trie, nina, emilija, 0, true) ? "Nina" : "Emilija")<<"\n";    
    
    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...