Submission #1229769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229769		opop1omar	Vlak (COCI20_vlak)	C++17	70 / 70	14 ms	24132 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;
    }

    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 sol(string s, int c) {
    bool hasValidMove = false;

    for (int i = 0; i < 26; ++i) {
        char w = 'a' + i;
        string temp = s + w;
        bool canMove = false;
        if (c == 0) canMove = (a.CountPrefix(temp) > 0);
        else canMove = (b.CountPrefix(temp) > 0);

        if (canMove) {
            hasValidMove = true;
            if (!sol(temp, c^1)) return true;
        }
    }
    if (!hasValidMove) return false;
    return false;
}
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);
    }

    cout<<(sol("",0)==1?"Nina\n":"Emilija\n");
}
signed main() {
    Ah_Ya_Alisson_Ah
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

• 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