Submission #1308377

#TimeUsernameProblemLanguageResultExecution timeMemory
1308377a5a7Vlak (COCI20_vlak)C++20
70 / 70
13 ms9904 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int trie[1000000][26];
bool nina[1000000];
bool emilija[1000000];
bool wins[1000000];
int nodes = 1;

void add_nina(string s){
    int current = 0;
    int cnt = 0;
    for (char c : s){
        if (trie[current][c-'a'] == 0){
            trie[current][c-'a'] = nodes++;
        }
        cnt++;
        current = trie[current][c-'a'];
        nina[current] = true;
    }
}

void add_emilija(string s){
    int current = 0;
    int cnt = 0;
    for (char c : s){
        if (trie[current][c-'a'] == 0){
            trie[current][c-'a'] = nodes++;
        }
        cnt++;
        current = trie[current][c-'a'];
        emilija[current] = true;
    }
}

bool does_it_win(int current, int cnt){
    bool yes = false;
    for (int i = 0; i < 26; i++){
        if (trie[current][i] == 0) continue;
        if (cnt == 0 && !nina[trie[current][i]]) continue;
        if (cnt == 1 && !emilija[trie[current][i]]) continue;
        does_it_win(trie[current][i], cnt^1);
        if (!wins[trie[current][i]]){
            yes = true;
            break;
        }
    }
    wins[current] = yes;
    return yes;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 0; i < n; i++){
        string s; cin >> s;
        add_nina(s);
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++){
        string s; cin >> s;
        add_emilija(s);
    }
    cout << (does_it_win(0, 0) ? "Nina" : "Emilija") << endl;
}
#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...