제출 #1140544

#제출 시각아이디문제언어결과실행 시간메모리
1140544huoiVlak (COCI20_vlak)C++17
70 / 70
12 ms20296 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1e18

struct Trie {
    struct Node {
        Node *child[26];
        bool n, e;

        Node() {
            for (int i = 0; i < 26; i++) child[i] = nullptr;
            n = e = false;
        }
    };

    Node *root;

    Trie() {
        root = new Node();
    }

    void add_string(string s, int player) {
        Node *u = root;
        for (char c : s) {
            int v = c - 'a';
            if (u->child[v] == nullptr) {
                u->child[v] = new Node();
            }
            u = u->child[v];
        }
        if (player == 0) u->n = true;
        if (player == 1) u->e = true;
    }

    int winner(Node *u, int player) {
        bool leaf = true;
        for (int v = 0; v < 26; v++)
            if (u->child[v] != nullptr)
                leaf = false;
        if (leaf) {
            if (u->n && !u->e) return 0;
            if (u->e && !u->n) return 1;
            return !player;
        }

        for (int v = 0; v < 26; v++) {
            if (u->child[v] == nullptr) continue;
            if (winner(u->child[v], !player) == player) return player;
        }
        return !player;
    }
};

void solve() {
    Trie trie;
    for (int player = 0; player <= 1; player++) {
        int n; cin >> n;
        while (n--) {
            string s; cin >> s;
            trie.add_string(s, player);
        }
    }

    vector<string> ans = {"Nina", "Emilija"};
    cout << ans[trie.winner(trie.root, 0)];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    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...