Submission #1137014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137014		toast12	Vlak (COCI20_vlak)	C++20	20 / 70	25 ms	23188 KiB

Main

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

const int K = 26;

struct vertex {
    int next[K];
    int end = 0;
    bool winnable_n = false, winnable_e = false; // who can win if they land on this node?
    bool n = false, e = false;
    vertex() {
        fill(next, next+K, -1);
    };
};

vector<vertex> trie(1);

void add_string(string s, bool e) {
    int v = 0;
    for (int i = 0; i < s.length(); i++) {
        int c = s[i]-'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        if (e) trie[v].e = true;
        else trie[v].n = true;
        v = trie[v].next[c];
    }
    trie[v].end++;
}

vector<vector<bool>> dp, ready;

bool solve(int v, int turn) {
    // turn = 0 --> nina
    // turn = 1 --> emilija
    if (ready[v][turn]) return dp[v][turn];
    if (turn == 1 && !trie[v].e) return false;
    if (turn == 0 && !trie[v].n) return false;
    if (trie[v].end) {
        if (turn == 1) {
            trie[v].winnable_e = true;
            return true;
        }
        else {
            trie[v].winnable_n = true;
            return true;
        }
    }
    bool ans = false;
    for (int i = 0; i < K; i++) {
        if (trie[v].next[i] != -1) ans |= !solve(trie[v].next[i], 1-turn);
    }
    ready[v][turn] = true;
    return dp[v][turn] = ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add_string(s, true);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        add_string(s, false);
    }
    ready.resize(trie.size()+1, vector<bool>(2));
    dp.resize(trie.size()+1, vector<bool>(2));
    if (solve(0, 0)) cout << "Nina\n";
    else cout << "Emilija\n";
    return 0;
}

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