oj.uz

Submission #871783

# Submission time Handle Problem Language Result Execution time Memory
871783 2023-11-11T15:12:53 Z rastervc Vlak (COCI20_vlak) C++17
70 / 70
 22 ms 20372 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19292 KB Output is correct
2 Correct 11 ms 18012 KB Output is correct
3 Correct 11 ms 16980 KB Output is correct
4 Correct 14 ms 18776 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19548 KB Output is correct
2 Correct 22 ms 20372 KB Output is correct
3 Correct 11 ms 18780 KB Output is correct
4 Correct 11 ms 19288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18524 KB Output is correct
2 Correct 11 ms 18012 KB Output is correct
3 Correct 11 ms 18536 KB Output is correct
4 Correct 14 ms 19792 KB Output is correct