Submission #377396

#	Time	Username	Problem	Language	Result	Execution time	Memory
377396		NONAME	Vlak (COCI20_vlak)	C++17	70 / 70	256 ms	106220 KiB

Main

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n, m, total;

struct st {
    int nxt[26];
    bool have[2];

    st() {
        for (int i = 0; i < 26; ++i) {
            nxt[i] = -1;
        }
        have[0] = have[1] = false;
    }
} trie[(int)(1e6)];

void add(string& s, int tp) {
    int v = 0;
    for (int i = 0; i < (int)(s.size()); ++i) {
        int j = s[i] - 'a';
        if (trie[v].nxt[j] == -1) {
            trie[v].nxt[j] = ++total;
        }
        trie[v].have[tp] = true;
        v = trie[v].nxt[j];
    }
    trie[v].have[tp] = true;
}

bool solve(int v, int tp) {
    for (int i = 0; i < 26; ++i) {
        if ((trie[v].nxt[i] == -1) || !trie[trie[v].nxt[i]].have[tp]) {
            continue;
        }

        bool f = solve(trie[v].nxt[i], tp ^ 1);

        if (!f) {
            // cerr << v << " " << 1 << "\n";
            return true;
        }
    }
    // cerr << v << " " << 0 << "\n";
    return false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        add(s, 0);
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        add(s, 1);
    }

    cout << (solve(0, 0) ? "Nina" : "Emilija") << "\n";

    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