Submission #1137016

#TimeUsernameProblemLanguageResultExecution timeMemory
1137016toast12Vlak (COCI20_vlak)C++20
70 / 70
17 ms14400 KiB
#include <bits/stdc++.h>
using namespace std;

const int K = 26;

struct vertex {
    int next[K];
    bool person[2];
    vertex() {
        fill(next, next+K, -1);
    };
};

vector<vertex> trie(1);

void add_string(string s, int p) {
    int v = 0;
    for (int i = 0; i < s.length(); i++) {
        int c = s[i]-'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        trie[v].person[p] = true;
        v = trie[v].next[c];
    }
}

bool solve(int v, int turn) {
    // turn = 0 --> nina
    // turn = 1 --> emilija
    bool ans = false;
    for (int i = 0; i < K; i++) {
        if (trie[v].person[turn]) {
            if (trie[v].next[i] != -1) ans |= !solve(trie[v].next[i], 1-turn);
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add_string(s, 0);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        add_string(s, 1);
    }
    if (solve(0, 0)) cout << "Nina\n";
    else cout << "Emilija\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...