제출 #1342087

#제출 시각아이디문제언어결과실행 시간메모리
1342087po_rag526Vlak (COCI20_vlak)C++20
0 / 70
19 ms25204 KiB
// dmoj problem: https://vjudge.net/contest/799391#problem/B
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;

int nxt;
int n, m;
map<char, int> trie[200001][2];
void push(char c, int root, int idx) {
    if (!trie[root][idx].count(c))
        trie[root][idx][c] = ++nxt;
}
bool wins(int plr, int cur[]) {
    bool out = false;
    for (auto [mv, nxt] : trie[cur[plr]][plr])
    {
        if (!trie[cur[(plr + 1) % 2]][(plr + 1) % 2].count(mv)) return true;
        int nc[2];
        nc[plr] = nxt;
        nc[(plr + 1) % 2] = trie[cur[(plr + 1) % 2]][(plr + 1) % 2][mv];
        out |= !wins((plr + 1) % 2, nc);
    }
    return out;
}
int32_t main() {
    cin.sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string a;
        cin >> a;
        int cur = 0;
        for (int j = 0; j < a.length(); j++)
        {
            push(a[j], cur, 0);
            cur = trie[cur][0][a[j]];
        }
    }
    cin >> m;
    nxt = 0;
    for (int i = 0; i < m; i++)
    {
        string a;
        cin >> a;
        int cur = 0;
        for (int j = 0; j < a.length(); j++)
        {
            push(a[j], cur, 1);
            cur = trie[cur][1][a[j]];
        }
    }
    cout << (wins(0, new int[] {0, 0}) ? "Nina" : "Emilja") << "\n";

    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...