Submission #1195085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195085		KindaGoodGames	Vlak (COCI20_vlak)	C++20	50 / 70	21 ms	12716 KiB

Main

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

struct TrieNode {
    vector<int> child;
    bool marked;
    bool p1;
    bool p2;

    TrieNode() {
        child.resize(26, -1);
        marked = false;
        p1 = false;
        p2 = false;
    }
};

vector<TrieNode> trie;
vector<vector<bool>> dp(2, { false });

void insert(string& s, int i, int ind, int k) {
    if (i + 1 == s.size()) {
        trie[ind].marked = true;
        return;
    }

    if (trie[ind].child[s[i] - 'a'] == -1) {
        trie[ind].child[s[i] - 'a'] = trie.size();
        trie.push_back(TrieNode());
    }
    int c = trie[ind].child[s[i] - 'a'];

    if (k == 0) {
        trie[c].p1 = true;
    }
    else {
        trie[c].p2 = true;
    }
    insert(s, i + 1, c, k);
}

void rec(int ind, int k) {
    if (trie[ind].p1 && !trie[ind].p2) {
        dp[0][ind] = 1;
        return;
    }
    if (trie[ind].p1 == false && trie[ind].p2 == true) {
        dp[1][ind] = 1;
        return;
    }
    bool ch = false;
    for (int i = 0; i < 26; i++) {
        int c = trie[ind].child[i];
        if (c != -1) {
            ch = true;
            rec(c, 1 - k);
            if (!dp[1 - k][c]) {
                dp[k][ind] = true;
            }
            if (!dp[k][c]) {
                dp[1 - k][ind] = true;
            }
        }
    }
    if (!ch) {
        dp[k][ind] = 1;
    }
}


int main() {
    trie.push_back(TrieNode());
    int n1;
    cin >> n1;

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

    int n2;
    cin >> n2;

    if (n1 == 0) {
        cout << "Emilija" << endl;
        return 0;
    }
    if (n2 == 0) {
        cout << "Nina" << endl;
        return 0;
    }

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

    dp = vector<vector<bool>>(2, vector<bool>(trie.size()));
    rec(0, 0);

    if (dp[0][0]) {
        cout << "Nina" << endl;
    }
    else {
        cout << "Emilija" << endl;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10