Submission #1020205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020205		icebear	Vlak (COCI20_vlak)	C++14	70 / 70	22 ms	20392 KiB

Main

// ~~ 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10