This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
int trie[mxN][26], dp[mxN];
int cnt = 0;
bool stop[mxN][2];
string alpha = "abcdefghijklmnopqrstuvwxyz";
void insert(string s, int flag) {
int node = 0;
for(auto c : s) {
if(trie[node][c-'a'] == 0) trie[node][c-'a'] = ++cnt;
node = trie[node][c-'a'];
}
stop[node][flag] = true;
}
void dfs(int node, int lvl) {
if(lvl & 1) dp[node] = 1;
else dp[node] = 2;
bool leaf = true;
for(auto c : alpha) {
int k = trie[node][c-'a'];
if(k) {
dfs(k, lvl+1);
leaf = false;
if(lvl & 1) dp[node] = max(dp[node], dp[k]);
else dp[node] = min(dp[node], dp[k]);
}
}
if(leaf) {
if(stop[node][0] && stop[node][1]) {
if(lvl & 1) dp[node] = 1;
else dp[node] = 2;
}
else if(stop[node][0]) dp[node] = 1;
else dp[node] = 2;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
insert(s, 0);
}
int m;
cin >> m;
for(int i = 0; i < m; i++) {
string s;
cin >> s;
insert(s, 1);
}
dfs(0, 0);
cout << (dp[0] == 1 ? "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... |