Submission #1308377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308377		a5a7	Vlak (COCI20_vlak)	C++20	70 / 70	13 ms	9904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int trie[1000000][26];
bool nina[1000000];
bool emilija[1000000];
bool wins[1000000];
int nodes = 1;

void add_nina(string s){
    int current = 0;
    int cnt = 0;
    for (char c : s){
        if (trie[current][c-'a'] == 0){
            trie[current][c-'a'] = nodes++;
        }
        cnt++;
        current = trie[current][c-'a'];
        nina[current] = true;
    }
}

void add_emilija(string s){
    int current = 0;
    int cnt = 0;
    for (char c : s){
        if (trie[current][c-'a'] == 0){
            trie[current][c-'a'] = nodes++;
        }
        cnt++;
        current = trie[current][c-'a'];
        emilija[current] = true;
    }
}

bool does_it_win(int current, int cnt){
    bool yes = false;
    for (int i = 0; i < 26; i++){
        if (trie[current][i] == 0) continue;
        if (cnt == 0 && !nina[trie[current][i]]) continue;
        if (cnt == 1 && !emilija[trie[current][i]]) continue;
        does_it_win(trie[current][i], cnt^1);
        if (!wins[trie[current][i]]){
            yes = true;
            break;
        }
    }
    wins[current] = yes;
    return yes;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 0; i < n; i++){
        string s; cin >> s;
        add_nina(s);
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++){
        string s; cin >> s;
        add_emilija(s);
    }
    cout << (does_it_win(0, 0) ? "Nina" : "Emilija") << endl;
}

• 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