Submission #1227802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227802		opop1omar	Vlak (COCI20_vlak)	C++17	0 / 70	347 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define Ah_Ya_Alisson_Ah ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long

struct Trie {
    struct Node {
        Node* child[26];
        int IsEnd, Prefix;
        Node() {
            memset(child, 0, sizeof child);
            IsEnd = Prefix = 0;
        }
    };
    Node* root = new Node();

    void insert(string &s) {
        Node* cur = root;
        for (auto it : s) {
            int idx = it - 'a';
            if (cur->child[idx] == 0) {
                cur->child[idx] = new Node();
            }
            cur = cur->child[idx];
            cur->Prefix++;
        }
        cur->IsEnd++;
    }
};

Trie a, b;

// dp[curA][curB][turn] = true if current player can force a win
map<pair<Trie::Node*, int>, bool> memo[2];

bool dp(Trie::Node* cur, int c) {
    if (memo[c].count({cur, c})) return memo[c][{cur, c}];

    bool canWin = false;
    for (int i = 0; i < 26; i++) {
        if (c == 0) { // Player A
            if (cur->child[i]) {
                if (!dp(b.root, 1)) { // If opponent loses after this move, we can force a win
                    canWin = true;
                    break;
                }
            }
        } else { // Player B
            if (cur->child[i]) {
                if (!dp(a.root, 0)) {
                    canWin = true;
                    break;
                }
            }
        }
    }

    return memo[c][{cur, c}] = canWin;
}

void solve() {
    int n;
    cin >> n;
    while (n--) {
        string s; cin >> s;
        a.insert(s);
    }
    cin >> n;
    while (n--) {
        string s; cin >> s;
        b.insert(s);
    }

    bool result = dp(a.root, 0);
    cout << (result ? "Nina\n" : "Emilija\n");
}

signed main() {
    Ah_Ya_Alisson_Ah
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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