oj.uz

Submission #542025

# Submission time Handle Problem Language Result Execution time Memory
542025 2022-03-25T07:51:21 Z AlperenT Vlak (COCI20_vlak) C++17
70 / 70
 30 ms 20372 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;

string str;

struct Trie{
    struct TrieNode{
        char color, winner;

        TrieNode* edge[26];

        TrieNode(){
            color = winner = '.';
            fill(edge, edge + 26, nullptr);
        }
    };

    TrieNode *root;

    void add(TrieNode *&v, string &str, char c, int indx = 0){
        if(!v) v = new TrieNode();

        if(indx == str.size()){
            if(v->color == '.') v->color = c;
            else if(v->color != c) v->color = 'C';
        }
        else{
            add(v->edge[str[indx] - 'a'], str, c, indx + 1);
        }
    }

    void dfs(TrieNode *&v, int p){
        if(!v) return;

        bool issame = false;

        for(int e = 0; e < 26; e++){
            if(v->edge[e]){
                dfs(v->edge[e], p == 'A' ? 'B' : 'A');

                if((v->edge[e]->color == p || v->edge[e]->color == 'C') && v->edge[e]->winner == p) issame = true;

                if(v->edge[e]->color == 'A'){
                    if(v->color == 'B') v->color = 'C';
                    else if(v->color == '.') v->color = 'A';
                }
                else if(v->edge[e]->color == 'B'){
                    if(v->color == 'A') v->color = 'C';
                    else if(v->color == '.') v->color = 'B';
                }
                else if(v->edge[e]->color == 'C'){
                    v->color = 'C';
                }
            }
        }

        v->winner = issame ? p : (p == 'A' ? 'B' : 'A');
    }
};

Trie trie;

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

    cin >> n;

    while(n--){
        cin >> str;

        trie.add(trie.root, str, 'A');
    }

    cin >> m;

    while(m--){
        cin >> str;

        trie.add(trie.root, str, 'B');
    }

    trie.dfs(trie.root, 'A');

    if(trie.root->winner == 'A') cout << "Nina";
    else cout << "Emilija";
}

Compilation message

Main.cpp: In member function 'void Trie::add(Trie::TrieNode*&, std::string&, char, int)':
Main.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(indx == str.size()){
      |            ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 580 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19052 KB Output is correct
2 Correct 27 ms 17868 KB Output is correct
3 Correct 27 ms 16968 KB Output is correct
4 Correct 30 ms 18696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 19472 KB Output is correct
2 Correct 26 ms 20372 KB Output is correct
3 Correct 26 ms 18744 KB Output is correct
4 Correct 25 ms 19036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18504 KB Output is correct
2 Correct 21 ms 18004 KB Output is correct
3 Correct 26 ms 18516 KB Output is correct
4 Correct 30 ms 19628 KB Output is correct