oj.uz

Submission #531338

# Submission time Handle Problem Language Result Execution time Memory
531338 2022-02-28T13:12:55 Z speedyArda Vlak (COCI20_vlak) C++14
70 / 70
 38 ms 30348 KB 
#include "bits/stdc++.h"

using namespace std;

const int MAXN = 2e6 + 20;
const int ALPHABET = 28;
struct trie_node 
{
    long long next_node[ALPHABET];
    bool leaf;
    int state = 0;
    trie_node() 
    {
        fill(next_node, next_node + ALPHABET, -1);
    }
};

vector<trie_node> trie;

void add_string(string input, int mask) 
{
    long long v = 0;
    for(char ch : input) 
    {
        trie[v].state |= mask;
        int c = ch - 'a';
        if(trie[v].next_node[c] == -1)
        {
            trie[v].next_node[c] = trie.size();
            trie.emplace_back();
        } 
        v = trie[v].next_node[c];
        
        
    }
    trie[v].leaf = true;
}

bool dfs_nina(int v, int depth) 
{

    if(!(trie[v].state & (1 << depth)))
        return false;
    for(int i = 0; i < ALPHABET; i++) 
    {
        if(trie[v].next_node[i] != -1 && !dfs_nina(trie[v].next_node[i], depth ^ 1)) 
            return true;
        
    }
   
    return false;
}

int main() 
{
    trie_node root = trie_node();
    //root.state = 3;
    trie.push_back(root);
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        string input;
        cin >> input;
        add_string(input, (1 << 0));
    }

    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        string input;
        cin >> input;
        add_string(input, (1 << 1));
    }

    if(dfs_nina(0, 0))
        cout << "Nina\n";
    else
        cout << "Emilija\n";
    
    
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30140 KB Output is correct
2 Correct 28 ms 30212 KB Output is correct
3 Correct 30 ms 30200 KB Output is correct
4 Correct 38 ms 30228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 30132 KB Output is correct
2 Correct 29 ms 30304 KB Output is correct
3 Correct 32 ms 30348 KB Output is correct
4 Correct 36 ms 30264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30208 KB Output is correct
2 Correct 29 ms 30224 KB Output is correct
3 Correct 29 ms 30248 KB Output is correct
4 Correct 32 ms 30252 KB Output is correct