Submission #1140543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140543		huoi	Vlak (COCI20_vlak)	C++17	70 / 70	26 ms	20292 KiB

Main

#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, int depth = 0) {
        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;
            int w = winner(u->child[v], !player, depth + 1);
            if (w == 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10