oj.uz

Submission #1019984

# Submission time Handle Problem Language Result Execution time Memory
1019984 2024-07-11T11:45:55 Z vjudge1 Vlak (COCI20_vlak) C++17
0 / 70
 19 ms 19292 KB 
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

struct Trie{
    struct Node{
        Node *child[26];
        bool canNinawin;
        int owner; // 2^0 is Nina, 2^1 is Emilija
        Node(){
            for(int i=0; i<26; ++i) child[i] = NULL;
            canNinawin = false;
            owner = 0;
        }
    } ;
    
    Node *root;
    Trie() {root = new Node(); }
    
    void add(string s, int who){
        Node *p = root;
        for(char c : s){
            int pos = c - 'a';
            if (p -> child[pos] == NULL) p -> child[pos] = new Node();
            p = p -> child[pos];
            p -> owner |= (1 << who);
        }
    }
    
   bool dfs(Node *p, int turn){
        bool ok = false;
        for(int pos = 0; pos < 26; ++pos){
            if (p -> child[pos] == NULL) continue;
            int t = p -> child[pos] -> owner;
            if ((t >> turn) & 1){
                ok = true;
                p -> canNinawin |= dfs(p -> child[pos], turn ^ 1);
            }
        }
        
        if (ok == false) return (turn == 1); // Emilija can't make move
        return (p -> canNinawin);
    }
} trie;

int main(){
    // freopen("icebearat.inp", "r", stdin);
    // freopen("icebearat.out", "w", stdout);
    int n, m; string s;
    cin >> n;
    while(n--){
        cin >> s;
        trie.add(s, 0);
    }
    
    cin >> m;
    while(m--){
        cin >> s;
        trie.add(s, 1);
    }
    
    trie.dfs(trie.root, 0);
    cout << (trie.root -> canNinawin ? "Nina" : "Emilija");
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 0 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 0 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18856 KB Output is correct
2 Incorrect 19 ms 17752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 18268 KB Output isn't correct
2 Halted 0 ms 0 KB -