oj.uz

답안 #649081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649081 2022-10-09T09:09:56 Z Elias_Obeid Vlak (COCI20_vlak) C++17
70 / 70
 24 ms 21644 KB 
#include <bits/stdc++.h>
using namespace std;

const int A = 26;
const int LEN = 200'000;

struct TrieNode
{
    array<bool, 2> players;
    array<int, A> next_nodes;
    TrieNode()
    {
        players.fill(false);
        next_nodes.fill(-1);
    }
};

int N, M;
int current_trie_node = 0;
array<TrieNode, LEN + 1> trie;

int fetchNode()
{
    trie[current_trie_node] = TrieNode();
    return current_trie_node++;
}

const int ROOT = fetchNode();

void addString(const string &S, int player)
{
    int current_node = ROOT;
    for (int i = 0; i < (int)S.size(); ++i)
    {
        int letter = (S[i] - 'a');
        if (trie[current_node].next_nodes[letter] == -1)
        {
            trie[current_node].next_nodes[letter] = fetchNode();
        }
        current_node = trie[current_node].next_nodes[letter];
        trie[current_node].players[player] = true;
    }
}

bool getWinner(int node, int player)
{
    bool won = false;
    for (int letter = 0; letter < A; ++letter)
    {
        if (trie[node].next_nodes[letter] != -1 &&
            trie[trie[node].next_nodes[letter]].players[player])
        {
            won |= !getWinner(trie[node].next_nodes[letter], player ^ 1);
        }
    }
    return won;
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        string S;
        cin >> S;
        addString(S, 0);
    }

    cin >> M;
    for (int i = 0; i < M; ++i)
    {
        string S;
        cin >> S;
        addString(S, 1);
    }
    cout << (getWinner(ROOT, 0) ? "Nina" : "Emilija") << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 10 ms 21332 KB Output is correct
4 Correct 10 ms 21360 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 9 ms 21332 KB Output is correct
4 Correct 11 ms 21324 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 11 ms 21332 KB Output is correct
4 Correct 10 ms 21440 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 9 ms 21440 KB Output is correct
4 Correct 12 ms 21436 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 21520 KB Output is correct
2 Correct 22 ms 21644 KB Output is correct
3 Correct 24 ms 21584 KB Output is correct
4 Correct 24 ms 21624 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 21636 KB Output is correct
2 Correct 23 ms 21636 KB Output is correct
3 Correct 20 ms 21588 KB Output is correct
4 Correct 23 ms 21640 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21540 KB Output is correct
2 Correct 21 ms 21636 KB Output is correct
3 Correct 21 ms 21616 KB Output is correct
4 Correct 22 ms 21588 KB Output is correct