Submission #1019984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019984		vjudge1	Vlak (COCI20_vlak)	C++17	0 / 70	19 ms	19292 KiB

Main

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