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<iostream>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<algorithm>
#define int long long int
#define vec vector<int>
#define endl '\n'
#define f(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
using namespace std;
class Node{
public:
int end;
int count1, count2;
vector<Node*>arr;
Node(){
end = 0;
count1 = 0;
count2 = 0;
arr.resize(26, NULL);
}
};
class Trie{
public:
Node* root;
//vec dp;
map<pair<Node*, int>, int>dp;
Trie(){
root = NULL;
//dp.resize(5005, -1);
}
void insert(string &t, int x){
if(!root) root = new Node();
Node* curr = root;
int n = t.length();
f(i, n){
int c = t[i] - 'a';
if(curr->arr[c] == NULL){
curr->arr[c] = new Node();
}
if(x == 0) curr->arr[c]->count1++;
else curr->arr[c]->count2++;
if(i == n-1){
curr->arr[c]->end=1;
}
curr = curr->arr[c];
}
}
// int getPrefixCount(string &t){
// Node* curr = root;
// int n = t.length(); int ans = 0;
// f(i, n){
// int c = t[i] - 'a';
// if(curr->arr[c] == NULL){
// break;
// }
// if(i == n-1){
// ans = curr->arr[c]->count;
// }
// curr = curr->arr[c];
// }
// return ans;
// }
// int totalWays(string &t, int i){
// int n = t.length();
// if(i == n) return 1;
// if(dp[i] != -1) return dp[i];
// int ans = 0;
// Node* curr = root;
// for(int k=i;k<n;k++){
// int c = t[k] - 'a';
// if(curr->arr[c] == NULL) break;
// if(curr->arr[c]->end) (ans += totalWays(t,k+1))%=mod;
// curr = curr->arr[c];
// }
// return dp[i] = ans;
// }
int rec(Node* curr, int turn){
if(curr == NULL) return 0;
if(dp.find({curr, turn}) != dp.end()) return dp[{curr, turn}];
int win = 0;
f(j, 26){
if(curr->arr[j] == NULL) continue;
if(turn == 0){
if(curr->arr[j]->count1){
win |= !rec(curr->arr[j], !turn);
}
}else{
if(curr->arr[j]->count2){
win |= !rec(curr->arr[j], !turn);
}
}
}
return dp[{curr, turn}] = win;
}
};
signed main(){
int m,n; cin>>m;
Trie *trie = new Trie();
while(m--){
string t; cin>>t;
trie->insert(t, 0);
}
cin>>n;
while(n--){
string t; cin>>t;
trie->insert(t, 1);
}
cout<<(trie->rec(trie->root, 0) ? "Nina" : "Emilija");
}
# | 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... |