Submission #947952

#TimeUsernameProblemLanguageResultExecution timeMemory
947952Magneto_Vlak (COCI20_vlak)C++14
70 / 70
31 ms26972 KiB
#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 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...