제출 #1137015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137015		toast12	Vlak (COCI20_vlak)	C++20	20 / 70	15 ms	14764 KiB

Main

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

const int K = 26;

struct vertex {
    int next[K];
    int end = 0;
    bool person[2];
    vertex() {
        fill(next, next+K, -1);
    };
};

vector<vertex> trie(1);

void add_string(string s, int p) {
    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();
        }
        trie[v].person[p] = true;
        v = trie[v].next[c];
    }
    trie[v].end++;
}

bool solve(int v, int turn) {
    // turn = 0 --> nina
    // turn = 1 --> emilija
    bool ans = false;
    for (int i = 0; i < K; i++) {
        if (trie[v].next[i] != -1 && trie[v].person[1-turn]) ans |= !solve(trie[v].next[i], 1-turn);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add_string(s, 0);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        add_string(s, 1);
    }
    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