제출 #1323347

#제출 시각아이디문제언어결과실행 시간메모리
1323347ezzatw122Vlak (COCI20_vlak)C++20
40 / 70
303 ms589824 KiB
#include <bits/stdc++.h> using namespace std; struct node { map<char, int> nxt; int &operator[](char c) { return nxt[c]; } }; struct trie { vector<node> t; int new_node() { t.push_back(node()); return (int) t.size() - 1; } trie() { t.clear(); new_node(); } void insert(string &s) { int u = 0; for (char &c: s) { if (!t[u][c]) { t[u][c] = new_node(); } u = t[u][c]; } } } tn, te; vector<vector<vector<int> > > dp; bool rc(int turn, int nina, int emilija) { auto &ret = dp[turn][nina][emilija]; if (~ret) return ret; bool win = false; int new_nina = nina, new_emilija = emilija; for (char c = 'a'; c <= 'z'; c++) { if (turn) { new_emilija = te.t[emilija][c]; if (!new_emilija) continue; if (!tn.t[nina][c]) { win = true; break; } auto ops = rc(0, tn.t[nina][c], new_emilija); if (!ops) { win = true; break; } } else { new_nina = tn.t[nina][c]; if (!new_nina) continue; if (!te.t[emilija][c]) { win = true; break; } auto ops = rc(1, new_nina, te.t[emilija][c]); if (!ops) { win = true; break; } } } return ret = win; } 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; tn.insert(s); } int m; cin >> m; for (int i = 0; i < m; i++) { string s; cin >> s; te.insert(s); } dp.assign(2, vector<vector<int> >(tn.t.size(), vector<int>(te.t.size(), -1))); cout << (rc(0, 0, 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...