제출 #1274139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274139		ngunguoi45	Vlak (COCI20_vlak)	C++17	70 / 70	26 ms	21652 KiB

Main

/*
    "Why do we fall? So we can learn how to pick ourselves up."
    - Alfred, Batman Begins -
*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define add emplace_back
#define MASK(i) (1LL << (i))
#define BIT(x,i) (((x) >> (i)) & 1)

using namespace std;
using pii = pair<int,int>;
using ll = long long;

const int maxn = 2e5+5;
const int oo = 1e9+7;

struct Node {
    Node *child[26];
    int has[2], dp;
    Node () {
        for (int i = 0;i < 26; i++) child[i] = nullptr;
        has[0] = has[1] = 0;
        dp = 0;
    }
};

struct Trie {
    Node *root;
    Trie () {
        root = new Node ();
    }
    void insert (const string &s, int type) {
        Node *p = root;
        for (auto c: s) {
            if (p->child[c-'a'] == nullptr) p->child[c-'a'] = new Node();
            p = p->child[c-'a'];
            p->has[type] = 1;
        }
    }
    void dfs (Node *p, int depth) {
        int id = depth%2;
        for (int i = 0;i < 26; i++) {
            if (p->child[i] == nullptr) continue;
            if (p->child[i]->has[id] && !p->child[i]->has[id^1]) p->dp = 1;
        }
        for (int i = 0;i < 26; i++) {
            if (p->child[i] == nullptr) continue;
            dfs (p->child[i], depth+1);
            p->dp |= (p->child[i]->dp^1);
        }
    }
};

int n, m;
string s;
Trie Wiki;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0;i < n; i++) {
        cin >> s;
        Wiki.insert(s, 0);
    }
    cin >> m;
    for (int i = 0;i < m; i++) {
        cin >> s;
        Wiki.insert(s, 1);
    }
    Wiki.dfs(Wiki.root, 0);
    Node *p = Wiki.root;
    cout << (p->dp ? "Nina" : "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