Submission #531338

#TimeUsernameProblemLanguageResultExecution timeMemory
531338speedyArdaVlak (COCI20_vlak)C++14
70 / 70
38 ms30348 KiB
#include "bits/stdc++.h"

using namespace std;

const int MAXN = 2e6 + 20;
const int ALPHABET = 28;
struct trie_node 
{
    long long next_node[ALPHABET];
    bool leaf;
    int state = 0;
    trie_node() 
    {
        fill(next_node, next_node + ALPHABET, -1);
    }
};

vector<trie_node> trie;

void add_string(string input, int mask) 
{
    long long v = 0;
    for(char ch : input) 
    {
        trie[v].state |= mask;
        int c = ch - 'a';
        if(trie[v].next_node[c] == -1)
        {
            trie[v].next_node[c] = trie.size();
            trie.emplace_back();
        } 
        v = trie[v].next_node[c];
        
        
    }
    trie[v].leaf = true;
}

bool dfs_nina(int v, int depth) 
{

    if(!(trie[v].state & (1 << depth)))
        return false;
    for(int i = 0; i < ALPHABET; i++) 
    {
        if(trie[v].next_node[i] != -1 && !dfs_nina(trie[v].next_node[i], depth ^ 1)) 
            return true;
        
    }
   
    return false;
}

int main() 
{
    trie_node root = trie_node();
    //root.state = 3;
    trie.push_back(root);
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        string input;
        cin >> input;
        add_string(input, (1 << 0));
    }

    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        string input;
        cin >> input;
        add_string(input, (1 << 1));
    }

    if(dfs_nina(0, 0))
        cout << "Nina\n";
    else
        cout << "Emilija\n";
    
    
}
#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...