Submission #1151300

#TimeUsernameProblemLanguageResultExecution timeMemory
1151300vanshmotwani16Vlak (COCI20_vlak)C++20
70 / 70
12 ms20296 KiB
// Humare saath Shri Raghunath toh
// Kis baat ki chinta :)

#include<bits/stdc++.h>
using namespace std;
//-----------------------------------------------------------------------------------------------------------------------//
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
typedef vector<pi> vp;
#define endl "\n"
#define all(_obj) _obj.begin(), _obj.end()
#define rev(i,a,b) for (ll i = b; i >= a; i--)
#define ff first
#define ss second
#define pb push_back
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define YES cout << "YES"
#define NO cout << "NO"
#define Yes cout << "Yes"
#define No cout << "No"
const ll M = 1e9 + 7;
//-----------------------------------------------------------------------------------------------------------------------//
bool cmp(pi &a, pi &b) {
    if (a.ff == b.ff) return a.ss > b.ss;
    else return a.ff > b.ff;
}
struct Node {
    Node* next[26];
    bool ez, n;
    Node() {
        ez = 0, n = 0;
        for (int i = 0; i < 26; i++) next[i] = nullptr;
    }
};
class Trie {
private:
    Node *root;
public:
    Trie() {
        root = new Node();
    }
    Node* top() {
        return root;
    }
    void insert(string &s, int player) {
        Node* curr = root;
        for (auto &x : s) {
            if (curr->next[x - 'a'] == nullptr) {
                curr->next[x - 'a'] = new Node();
            }
            curr = curr->next[x - 'a'];
        }
        if (player == 0) curr->n = 1;
        else curr->ez = 1;
    }
    int winner(Node* curr, int player) {
        bool leaf = 1;
        for (int i = 0; i < 26; i++) {
            if (curr->next[i] != nullptr) {
                leaf = 0; break;
            }
        }
        if (leaf) {
            if (curr->n == 1 && curr->ez == 1) return 1 ^ player;
            else if (curr->n == 1 && curr->ez == 0) return 0;
            else if (curr->n == 0 && curr->ez == 1) return 1;
        }
        for (int i = 0; i < 26; i++) {
            if (curr->next[i] != nullptr) {
                int w = winner(curr->next[i], 1 ^ player);
                if (w == player) return player;
            }
        }
        return 1 ^ player;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    Trie trie;
    Node* begin = trie.top();
    ll n;
    cin >> n;
    loop(i, 0, n) {
        string s;
        cin >> s;
        trie.insert(s, 0);
    }
    ll m;
    cin >> m;
    loop(i, 0, m) {
        string s;
        cin >> s;
        trie.insert(s, 1);
    }
    int win = trie.winner(begin, 0);
    (win == 0) ? cout << "Nina" : cout << "Emilija";
    cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...