Submission #1338454

#TimeUsernameProblemLanguageResultExecution timeMemory
1338454buzdiVlak (COCI20_vlak)C++20
70 / 70
9 ms9808 KiB
#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

const int TMAX = 2e5;
const int CMAX = 26;

int n, m, nodes = 1;
int trie[TMAX + 1][CMAX];
bool has[TMAX + 1][2];

void insert_word(string& s, int w) {
    int node = 1;
    for(char c : s) {
        int x = c - 'a';
        if(!trie[node][x]) {
            trie[node][x] = ++nodes;
        }
        node = trie[node][x];
        has[node][w] = 1;
    }
}

bool DFS(int node, int w) {
    for(int i = 0; i < CMAX; i++) {
        int next_node = trie[node][i];
        if(next_node && has[next_node][w] && !has[next_node][!w]) {
            return true;
        }
    }

    for(int i = 0; i < CMAX; i++) {
        int next_node = trie[node][i];
        if(next_node && has[next_node][0] && has[next_node][1]) {
            if(!DFS(next_node, !w)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert_word(s, 0);
    }

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

    cout << (DFS(1, 0) ? "Nina" : "Emilija");
    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...