Submission #1283288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283288		catsarecool5530	Vlak (COCI20_vlak)	C++20	70 / 70	16 ms	21168 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
#define int long long
const int MOD = 1e9 + 7;
const ll INF = 1e18;
 
const int N = 200005;

int trieA[N][26];
int trieB[N][26];
int nodeCount;

void insert(int trie[N][26], string& s) {
    int node = 1;
    for (char c : s) {
        if (trie[node][c-'a'] == 0) {
            trie[node][c-'a'] = ++nodeCount;
        }
        node = trie[node][c-'a'];
    }
}
const int Alice = 0;
const int Bob = 1;
bool rec(bool turn, int nodeA, int nodeB) {
    bool res = 0;
    if (turn == Alice) {
        if (nodeB == 0) return 1; // winner! 
        if (nodeA == 0) return 0; // loser! (but winner first)
        
        for (int next = 0; next < 26; next++) {
            res |= !rec(!turn, trieA[nodeA][next], trieB[nodeB][next]);
        }
        return res;
    } else {
        if (nodeA == 0) return 1;
        if (nodeB == 0) return 0;
        
        for (int next = 0; next < 26; next++) {
            res |= !rec(!turn, trieA[nodeA][next], trieB[nodeB][next]);
        }
        return res;
    }
}


void solve() {
    int n; cin >> n;
    vector<string> a(n);
    nodeCount = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(trieA, a[i]);
    }
    int m; cin >> m;
    vector<string> b(m);
    nodeCount = 1;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        insert(trieB, b[i]);
    }

    bool ans = rec(0, 1, 1);
    if (ans == 1) {
        cout << "Nina\n";
    } else {
        cout << "Emilija\n";
    }
}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    // freopen("island.in", "r", stdin);
    // freopen("ans.out", "w", stdout);
    ll t = 1; //cin >> t;
    while (t--) {
        solve();
    }
}

• 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