Submission #1323358

#TimeUsernameProblemLanguageResultExecution timeMemory
1323358shahodzVlak (COCI20_vlak)C++20
70 / 70
13 ms23892 KiB
#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 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...