oj.uz

Submission #1063647

# Submission time Handle Problem Language Result Execution time Memory
1063647 2024-08-17T22:07:02 Z dyogorb Vlak (COCI20_vlak) C++14
70 / 70
 16 ms 27228 KB 
#include <bits/stdc++.h>

using namespace std;
const int WMAX = 4e5 + 1;

int trie[WMAX][26];
int trie_flag_a[WMAX][26];
int trie_flag_b[WMAX][26];
int node_count;
bool stop[WMAX];

void insert(string word, int flag){
    int node = 0;
    for (char c: word)
    {
        if(trie[node][c - 'a'] == 0) trie[node][c - 'a'] = ++node_count;

        if(!flag)trie_flag_a[node][c - 'a'] = 1;
        else trie_flag_b[node][c - 'a'] = 1;
        node = trie[node][c - 'a'];
    }
    stop[node] = true;
}

int bfs(int node, int p){
    int found = 0;

    for (int i = 0; i < 26; i++)
    {
        if(p == 0){
            if(trie_flag_a[node][i] && !trie_flag_b[node][i]) found = 1;
        } else{
            if(trie_flag_b[node][i] && !trie_flag_a[node][i]) found = 1;
        }
    }
    if(found) return p;

    for (int i = 0; i < 26; i++)
    {
        if(p == 0 && trie_flag_a[node][i]){
            found |= bfs(trie[node][i], (p + 1) % 2) == p;
        } else if(p == 1 && trie_flag_b[node][i]){
            found |= bfs(trie[node][i], (p + 1) % 2) == p;
        }
    }
    if(found) return p;
    else return (p + 1) % 2;    
}


int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        insert(s, 0);
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        string s;
        cin >> s;
        insert(s, 1);
    }


    if(bfs(0, 0)){
        cout << "Emilija";
    } else{
        cout << "Nina";
    }

    cout << endl;    
    
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24412 KB Output is correct
2 Correct 16 ms 23132 KB Output is correct
3 Correct 14 ms 21852 KB Output is correct
4 Correct 13 ms 25692 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26456 KB Output is correct
2 Correct 11 ms 27228 KB Output is correct
3 Correct 10 ms 25692 KB Output is correct
4 Correct 11 ms 25948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25436 KB Output is correct
2 Correct 11 ms 25076 KB Output is correct
3 Correct 12 ms 25688 KB Output is correct
4 Correct 11 ms 26716 KB Output is correct