제출 #1227799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227799		opop1omar	Vlak (COCI20_vlak)	C++17	0 / 70	34 ms	22948 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define Ah_Ya_Alisson_Ah ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T rand(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
struct Trie {
    struct Node {
        Node* child[26];
        int IsEnd, Prefix;
        Node() {
            memset(child, 0, sizeof child);
            IsEnd = Prefix = 0;
        }
    };
    Node* root = new Node();

    void insert(string &s) {
        Node* cur = root;
        for (auto it : s) {
            int idx = it - 'a';
            if (cur->child[idx] == 0) {
                cur->child[idx] = new Node();
            }
            cur = cur->child[idx];
            cur->Prefix++;
        }
        cur->IsEnd++;
    }
    bool SearchWord(string &s) {
        Node* cur = root;
        for (auto it : s) {
            int idx = it - 'a';
            if (cur->child[idx] == 0) return false;
            cur = cur->child[idx];
        }
        return cur->IsEnd > 0;
    }

    int CountWord(string &s) {
        Node* cur = root;
        for (auto it : s) {
            int idx = it - 'a';
            if (cur->child[idx] == 0) return 0;
            cur = cur->child[idx];
        }
        return cur->IsEnd;
    }
    int CountPrefix(string &s) {
        Node* cur = root;
        for (auto it : s) {
            int idx = it - 'a';
            if (cur->child[idx] == 0) return 0;
            cur = cur->child[idx];
        }
        return cur->Prefix;
    }

    // Delete a word (reducing counts and deleting unused nodes)
    bool deleteWord(Node* cur, string &s, int depth) {
        if (depth == s.size()) {
            if (cur->IsEnd == 0) return false;
            cur->IsEnd--;
            cur->Prefix--;
            return true;
        }
        int idx = s[depth] - 'a';
        if (cur->child[idx] == 0) return false;
        bool deleted = deleteWord(cur->child[idx], s, depth + 1);
        if (deleted) {
            cur->Prefix--;
            // Delete node if no prefix remains
            if (cur->child[idx]->Prefix == 0) {
                delete cur->child[idx];
                cur->child[idx] = 0;
            }
        }
        return deleted;
    }

    bool Delete(string &s) {
        return deleteWord(root, s, 0);
    }
    // Find longest word length in the Trie
    void longest(Node* cur, int depth, int &maxLen) {
        if (cur->IsEnd > 0) maxLen = max(maxLen, depth);
        for (int i = 0; i < 26; i++) {
            if (cur->child[i]) {
                longest(cur->child[i], depth + 1, maxLen);
            }
        }
    }

    int LongestWordLength() {
        int maxLen = 0;
        longest(root, 0, maxLen);
        return maxLen;
    }

    // Check if any word is prefix of another word (e.g. for phone list consistency problems)
    bool hasPrefixConflict(Node* cur) {
        if (cur->IsEnd > 0 && cur->Prefix > cur->IsEnd) return true;
        for (int i = 0; i < 26; i++) {
            if (cur->child[i] && hasPrefixConflict(cur->child[i])) return true;
        }
        return false;
    }

    bool HasPrefixConflict() {
        return hasPrefixConflict(root);
    }
};
Trie a,b;
bool ok=0;
void sol(string s,int c) {
    int ww=0;
    for (int i=0;i<26;++i) {
        char w='a'+i;
        string temp=s;
        temp+=w;
        if(c==0) {
            if(a.CountPrefix(temp)==0) ww++;
            else sol(temp,c^1);
        }
        else {
            if(b.CountPrefix(temp)==0) ww++;
            else sol(temp,c^1);
        }
    }
    if(ww==26&&c==1) {
        ok=1;
    }
}
void solve() {
    int n;cin>>n;
    while(n--) {
        string s;cin>>s;
        a.insert(s);
    }
    cin>>n;
    while(n--) {
        string s;cin>>s;
        b.insert(s);
    }
    sol("",0);
    cout<<(ok==1?"Nina\n":"Emilija\n");
}
signed main() {
    Ah_Ya_Alisson_Ah
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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