Submission #1323349

#TimeUsernameProblemLanguageResultExecution timeMemory
1323349ezzatw122Vlak (COCI20_vlak)C++20
40 / 70
300 ms589824 KiB
#include <bits/stdc++.h>
using namespace std;

struct node {
    map<char, int> nxt;

    int &operator[](char c) {
        return nxt[c];
    }

    int get(char c) {
        auto it = nxt.find(c);
        if (it == nxt.end()) return 0;
        return it->second;
    }
};

struct trie {
    vector<node> t;

    int new_node() {
        t.push_back(node());
        return (int) t.size() - 1;
    }

    trie() {
        t.clear();
        new_node();
    }

    void insert(string &s) {
        int u = 0;
        for (char &c: s) {
            if (!t[u][c]) {
                t[u][c] = new_node();
            }
            u = t[u][c];
        }
    }
} tn, te;

vector<vector<vector<int> > > dp;

bool rc(int turn, int nina, int emilija) {
    auto &ret = dp[turn][nina][emilija];
    if (~ret) return ret;

    bool win = false;
    int new_nina = nina, new_emilija = emilija;
    for (char c = 'a'; c <= 'z'; c++) {
        if (turn) {
            new_emilija = te.t[emilija][c];

            if (!new_emilija) continue;
            if (!tn.t[nina].get(c)) {
                win = true;
                break;
            }

            auto ops = rc(0, tn.t[nina][c], new_emilija);
            if (!ops) {
                win = true;
                break;
            }
        } else {
            new_nina = tn.t[nina][c];

            if (!new_nina) continue;
            if (!te.t[emilija].get(c)) {
                win = true;
                break;
            }

            auto ops = rc(1, new_nina, te.t[emilija][c]);
            if (!ops) {
                win = true;
                break;
            }
        }
    }

    return ret = win;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        tn.insert(s);
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        te.insert(s);
    }

    dp.assign(2, vector<vector<int> >(tn.t.size(), vector<int>(te.t.size(), -1)));

    cout << (rc(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...