Submission #1195869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195869		anonymous321	Vlak (COCI20_vlak)	C++20	70 / 70	15 ms	13224 KiB

Main

// https://oj.uz/problem/view/COCI20_vlak
#include <bits/stdc++.h>
using namespace std;

struct node {
    vector<int> child = vector<int> (26, -1);
    bool nina = false;
    bool emilija = false;
};

vector<node> t {{}};

void insert (string &s, bool nina, int id = 0, int i = 0) {
    if (nina) {
        t[i].nina = true;
    } else {
        t[i].emilija = true;
    }
    if (s.size() == id) return;
    int c = s[id] - 'a';
    if (t[i].child[c] == -1) {
        t.push_back({});
        t[i].child[c] = t.size() - 1;
    }
    insert(s, nina, id+1, t[i].child[c]);
}

bool dfs (int i, bool nina) {
    bool win = false;
    for (int c = 0; c < 26; c++) {
        if (t[i].child[c] == -1) continue;
        if (nina && !t[t[i].child[c]].nina) continue;
        if (!nina && !t[t[i].child[c]].emilija) continue;
        if (!dfs(t[i].child[c], !nina)) {
            win = true;
        }
    }
    return win;
}

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;
        insert(s, true);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        insert(s, false);
    }
    
    if (dfs(0, true)) {
        cout << "Nina\n";
    } else {
        cout << "Emilija\n";
    }
    return 0;
}

• 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