Submission #1129350

#TimeUsernameProblemLanguageResultExecution timeMemory
1129350goats_9Vlak (COCI20_vlak)C++20
70 / 70
17 ms14204 KiB
/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Trie {
    const int K = 26;
    const char A = 'a';
    int cnt;
    vector<vector<int>> tr;
    vector<int> stop, id;
    Trie() {
        cnt = 1;
        id.assign(K, -1);
        tr.push_back(id);
        stop.push_back(0);
    }
    void add(string &s) {
        int node = 0;
        for (char ch : s) {
            if (tr[node][ch - A] == -1) {
                tr[node][ch - A] = cnt++;
                tr.push_back(id);
                stop.push_back(0);
            }
            node = tr[node][ch - A];
        }
        stop[node] = 1;
    }
    int find(string &s) {
        int node = 0;
        for (char ch : s) {
            if (tr[node][ch - A] == -1) return -1;
            node = tr[node][ch - A];
        }
        return node;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    Trie nina;
    while (n--) {
        string s;
        cin >> s;
        nina.add(s);
    }
    Trie emilija;
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        emilija.add(s);
    }
    function<bool(int, int, int)> go = [&] (int n, int e, int p) -> bool {
        for (int i = 0; i < nina.K; i++) {
            if (p == 0) {
                if (nina.tr[n][i] == -1) continue;
                if (emilija.tr[e][i] == -1) return true;
                if (!go(nina.tr[n][i], emilija.tr[e][i], p ^ 1)) return true;
            } else {
                if (emilija.tr[e][i] == -1) continue;
                if (nina.tr[n][i] == -1) return true;
                if (!go(nina.tr[n][i], emilija.tr[e][i], p ^ 1)) return true;
            }
        }
        return false;
    };
    cout << (go(0, 0, 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...