#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 time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |