제출 #1227803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227803		opop1omar	Vlak (COCI20_vlak)	C++17	0 / 70	384 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;
        int win[2]; // -1 = unvisited, 0 = lose, 1 = win

        Node() {
            memset(child, 0, sizeof child);
            memset(win, -1, sizeof win);
            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;

bool dp(Trie::Node* cur, int c) {
    if (cur->win[c] != -1) return cur->win[c];

    bool canWin = false;
    for (int i = 0; i < 26; i++) {
        if (cur->child[i]) {
            // Switch turns and call dp on other Trie root
            if (c == 0) { // Player A
                if (!dp(b.root, 1)) { // If opponent loses, current wins
                    canWin = true;
                    break;
                }
            } else { // Player B
                if (!dp(a.root, 0)) {
                    canWin = true;
                    break;
                }
            }
        }
    }
    return cur->win[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