Submission #871783

#	Time	Username	Problem	Language	Result	Execution time	Memory
871783		rastervc	Vlak (COCI20_vlak)	C++17	70 / 70	22 ms	20372 KiB

Main

#include <iostream>
#include <string>

using namespace std;

struct Trie {
    Trie *next[26]{};
    int player = -1;

    void insert(const char *str, int player) {
        if (!*str) return;
        const int ch = *str - 'a';
        if (!next[ch]) next[ch] = new Trie;
        if (next[ch]->player == -1) next[ch]->player = player;
        else if (next[ch]->player != player) next[ch]->player = 2;
        next[ch]->insert(str + 1, player);
    }

    bool can(int player, int depth) {
        if (player == 2) return true;
        return player == depth % 2;
    }

    bool is_winning(int depth = 0) {
        if (depth % 2 == 0) {
            bool winning = false;
            for (int i = 0; i < 26; ++i)
                if (next[i] && can(next[i]->player, depth))
                    winning = winning || next[i]->is_winning(depth + 1);
            return winning; 
        } else {
            bool winning = true;
            for (int i = 0; i < 26; ++i)
                if (next[i] && can(next[i]->player, depth))
                    winning = winning && next[i]->is_winning(depth + 1);
            return winning;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    string str;
    Trie *trie = new Trie;

    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> str;
        trie->insert(str.c_str(), 0);
    }

    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> str;
        trie->insert(str.c_str(), 1);
    }

    cout << (trie->is_winning() ? "Nina" : "Emilija");

    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