Submission #1129352

#TimeUsernameProblemLanguageResultExecution timeMemory
1129352weirdflexbutokVlak (COCI20_vlak)C++20
70 / 70
18 ms14328 KiB
/* Author: goats_9 */

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

using ll = long long;

struct Trie {
    vector<vector<int>> tr;
    vector<int> stop;
    vector<int> id;
    int cnt;
    const int K = 26;
    const char A = 'a';
    // Trie() : tr(vector<vector<int>> (1, vector<int> (K, -1))), stop(1, 0), cnt(1) {}
    Trie() {
        id.resize(K, -1);
        tr.push_back(id);
        stop.push_back(0);
        cnt = 1;
    }
    void add(string &s) {
        int node = 0;
        for (char ch : s) {
            // cerr << ch << '\n';
            if (tr[node][ch - A] == -1) {
                tr[node][ch - A] = cnt++;
                tr.push_back(id);
                // cerr << tr.size() << '\n';
                stop.push_back(0);
            }
            // // cerr << tr[node][ch - A] << '\n';
            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);
        // cerr << s << '\n';
    }
    Trie emilija;
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        emilija.add(s);
    }
    // cerr << m << '\n';
    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;
            } 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...