oj.uz

Submission #1020205

# Submission time Handle Problem Language Result Execution time Memory
1020205 2024-07-11T16:53:48 Z icebear Vlak (COCI20_vlak) C++14
70 / 70
 22 ms 20392 KB 
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

struct Trie{
    struct Node{
        Node *child[26];
        bool Ninawin;
        bool Ninas, Emilijas;
        Node(){
            for(int i=0; i<26; ++i) child[i] = NULL;
            Ninawin = true;
            Ninas = Emilijas = false;
        }
    } ;
    
    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];
            if (who == 0) p -> Ninas = true;
            else p -> Emilijas = true;
        }
    }
    
   bool dfs(Node *p, int turn){
        bool ok = false;
        // In Nina's turn, she just need to make one way to win
        // In Emlija's turn, Nina must make all way winning
        p -> Ninawin = (turn == 1);
        	
        for(int pos = 0; pos < 26; pos++) {
        	if (p -> child[pos] == NULL) continue;
        	if (turn == 0 && p -> child[pos] -> Ninas) 
        		ok = true, p -> Ninawin |= dfs(p -> child[pos], turn ^ 1);
        	else if (turn == 1 && p -> child[pos] -> Emilijas)
        		ok = true, p -> Ninawin &= dfs(p -> child[pos], turn ^ 1);
		}
        
        if (ok == false) p -> Ninawin = (turn == 1);
        return (p -> Ninawin);
    }
} 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 -> Ninawin ? "Nina" : "Emilija");
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.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 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 436 KB Output is correct

Subtask #4
10.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 600 KB Output is correct
4 Correct 0 ms 856 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19036 KB Output is correct
2 Correct 18 ms 18008 KB Output is correct
3 Correct 18 ms 16976 KB Output is correct
4 Correct 17 ms 18780 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19544 KB Output is correct
2 Correct 17 ms 20392 KB Output is correct
3 Correct 15 ms 18780 KB Output is correct
4 Correct 22 ms 19036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 18520 KB Output is correct
2 Correct 20 ms 18008 KB Output is correct
3 Correct 18 ms 18544 KB Output is correct
4 Correct 16 ms 19548 KB Output is correct