Submission #930877

#	Time	Username	Problem	Language	Result	Execution time	Memory
930877		woofes	Vlak (COCI20_vlak)	C++17	70 / 70	12 ms	16848 KiB

Main

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int cnt_s = 26;

struct node {
    int val;
    int lnk[cnt_s];
    bool st1;
    bool st2;
    node() {
        st1 = true;
        st2 = true;
        for (int i = 0; i < cnt_s; i++) {
            lnk[i] = -1;
        }
    }
    node(int v, bool s) {
        val = v;
        st1 = false;
        st2 = false;
        for (int i = 0; i < cnt_s; i++) {
            lnk[i] = -1;
        }
    }
};

vector<node> trie(1);

void add(string& s, int pd) {
    int v = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        int ind = s[s.size() - 1 - i] - 'a';
        int u = trie[v].lnk[ind];
        if (u == -1) {
            u = trie.size();
            trie[v].lnk[ind] = u;

            node nd(ind, false);
            trie.push_back(nd);
        }
        v = u;
        if (pd) {
            trie[v].st1 = true;
        } else {
            trie[v].st2 = true;
        }
    }
}

bool find_d(int v, int deep) {
    if (v == -1) {
        return 1;
    }
    if (deep % 2 == 0) {
        if (!trie[v].st1) {
            return 1;
        }
    } else {
        if (!trie[v].st2) {
            return 1;
        }
    }

    for (int i : trie[v].lnk) {
        if (!find_d(i, deep + 1)) {
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // freopen("input.txt", "r", stdin);

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s, 1);
    }
    int res = find_d(0, 0);
    if (!res) {
        cout << "Emilija";
    } else {
        cout << "Nina";
    }
}

• 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