Submission #1129352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129352		weirdflexbutok	Vlak (COCI20_vlak)	C++20	70 / 70	18 ms	14328 KiB

Main

/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Trie {
    vector<vector<int>> tr;
    vector<int> stop;
    vector<int> id;
    int cnt;
    const int K = 26;
    const char A = 'a';
    // Trie() : tr(vector<vector<int>> (1, vector<int> (K, -1))), stop(1, 0), cnt(1) {}
    Trie() {
        id.resize(K, -1);
        tr.push_back(id);
        stop.push_back(0);
        cnt = 1;
    }
    void add(string &s) {
        int node = 0;
        for (char ch : s) {
            // cerr << ch << '\n';
            if (tr[node][ch - A] == -1) {
                tr[node][ch - A] = cnt++;
                tr.push_back(id);
                // cerr << tr.size() << '\n';
                stop.push_back(0);
            }
            // // cerr << tr[node][ch - A] << '\n';
            node = tr[node][ch - A];
        }
        stop[node] = 1;
    }
    int find(string &s) {
        int node = 0;
        for (char ch : s) {
            if (tr[node][ch - A] == -1) return -1;
            node = tr[node][ch - A];
        }
        return node;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    Trie nina;
    while (n--) {
        string s;
        cin >> s;
        nina.add(s);
        // cerr << s << '\n';
    }
    Trie emilija;
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        emilija.add(s);
    }
    // cerr << m << '\n';
    function<bool(int, int, int)> go = [&] (int n, int e, int p) -> bool {
        for (int i = 0; i < nina.K; i++) {
            if (p == 0) {
                if (nina.tr[n][i] == -1) continue;
                if (emilija.tr[e][i] == -1) return true;
            } else {
                if (emilija.tr[e][i] == -1) continue;
                if (nina.tr[n][i] == -1) return true;
            }
            if (!go(nina.tr[n][i], emilija.tr[e][i], p ^ 1)) return true;
        }
        return false;
    };
    cout << (go(0, 0, 0) ? "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