Submission #1323358

#TimeUsernameProblemLanguageResultExecution timeMemory
1323358shahodzVlak (COCI20_vlak)C++20
70 / 70
13 ms23892 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

struct node {
    int nxt[26], cnt[2], lvl;

    node() {
        lvl = cnt[0] = cnt[1] = 0;
        memset(nxt, -1, sizeof(nxt));
    }
};

struct trie {
    int id = 1;
    vector<node> t;

    trie() {
        t.assign(N, node());
    }

    void insert(string &s, int turn) {
        int u = 0, lvl = 1;
        t[u].cnt[turn]++;
        for (char &c: s) {
            if (t[u].nxt[c - 'a'] == -1) {
                t[u].nxt[c - 'a'] = id++;
            }
            u = t[u].nxt[c - 'a'];
            t[u].lvl = lvl++;
            t[u].cnt[turn]++;
        }
    }
} tr;

int dp[N];

bool rc(int u) {
    auto &ret = dp[u];
    if (~ret) return ret;

    ret = 0;
    int turn = tr.t[u].lvl & 1;
    if (!tr.t[u].cnt[turn]) {
        return ret;
    }

    for (int c = 0; c < 26; c++) {
        if (~tr.t[u].nxt[c]) {
            ret |= (rc(tr.t[u].nxt[c]) == 0);
        }
    }
    return ret;
}

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;
        tr.insert(s, 0);
    }

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

    memset(dp, -1, sizeof(dp));

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