Submission #1137015

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

const int K = 26;

struct vertex {
    int next[K];
    int end = 0;
    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];
    }
    trie[v].end++;
}

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].next[i] != -1 && trie[v].person[1-turn]) 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...