Submission #401581

#TimeUsernameProblemLanguageResultExecution timeMemory
401581jenkinsserVlak (COCI20_vlak)C++17
70 / 70
30 ms33788 KiB
#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 2e5+5;
const int INF = 1e9+5;
const int mod = 1e9+7;

struct node{
    int kenarlar[26];
};

node trie1[N],trie2[N];
int n,m,nodesayisi1=1,nodesayisi2=1;
string s[N],t[N];

void ekle1(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie1[cur_node].kenarlar[c]==0){
            nodesayisi1++;
            trie1[cur_node].kenarlar[c]=nodesayisi1;
        }
        cur_node=trie1[cur_node].kenarlar[c];
    }
}

void ekle2(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie2[cur_node].kenarlar[c]==0){
            nodesayisi2++;
            trie2[cur_node].kenarlar[c]=nodesayisi2;
        }
        cur_node=trie2[cur_node].kenarlar[c];
    }
}

int bul1(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie1[cur_node].kenarlar[c]==0)
            return 0;
        cur_node=trie1[cur_node].kenarlar[c];
    }
    for(int i=0;i<26;i++)
        if(trie1[cur_node].kenarlar[i])
            return cur_node;
    return 0;
}

int bul2(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie2[cur_node].kenarlar[c]==0)
            return 0;
        cur_node=trie2[cur_node].kenarlar[c];
    }
    for(int i=0;i<26;i++)
        if(trie2[cur_node].kenarlar[i])
            return cur_node;
    return 0;
}

bool solve(string str,bool flag){
    // cout << str << sp << flag << nl;
    if(flag){
        int a=bul1(str);
        if(!a)
            return false;
        bool res=false;
        for(int i=0;i<26;i++){
            if(trie1[a].kenarlar[i]){
                res|=solve(str+char(i+'a'),!flag);
            }
        }
        return res;
    }
    else{
        int a=bul2(str);
        if(!a){
            // cout << str << nl;
            return true;
        }
        bool res=true;
        for(int i=0;i<26;i++){
            if(trie2[a].kenarlar[i]){
                // cout << str << sp << char(i+'a') << nl;
                res&=solve(str+char(i+'a'),!flag);
            }
        }
        return res;
    }
}

signed main(){
    fastio()
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        ekle1(s[i]);
    }
    cin >> m;
    for(int i=1;i<=m;i++){
        cin >> t[i];
        ekle2(t[i]);
    }
    bool res=false;
    for(int i=0;i<26;i++){
        if(trie1[1].kenarlar[i]){
            string str;
            str+=char('a'+i);
            res|=solve(str,0);
            // cout << str << sp << solve(str,0) << nl;
        }
    }
    if(res)
        cout << "Nina";
    else
        cout << "Emilija";
}

#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...