Submission #1172167

#TimeUsernameProblemLanguageResultExecution timeMemory
1172167karlsoosVlak (COCI20_vlak)C++20
0 / 70
24 ms18076 KiB
#include <iostream>
#include <vector>
using namespace std;
int ncount = 1;
void insert(string s, vector<pair<vector<bool>, vector<int>>> &t, int p, int i = 0, int v = 0){
    t[v].first[p] = 1;
    //cout<<s<<" "<<i<<" "<<v<<"\n";
    if(i == (int)s.size()){
        return;
    }
    if(t[v].second[s[i]-97] == -1){
        t[v].second[s[i]-97] = ncount++;
        t.push_back({vector<bool>(2,0), vector<int>(26,-1)});
    }

    insert(s, t, p, i+1, t[v].second[s[i]-97]);
}

int dfs(int v, vector<pair<vector<bool>, vector<int>>> &t, int z){
    //cout<<v<<"\n";  
    //abzweig
    int res = 0;
    bool e = 1;
    for(auto c : t[v].second){
        if(c != -1){
            //cout<<c<<"c\n";
            e = 0;
            if(!t[c].first[0] && t[c].first[1] && (z%2)){
                // res = 0;
                return 0;
            }
            if(t[c].first[0] && !t[c].first[1] && !(z%2)){
                // res = 1;
                return 1;
            }
            if(t[c].first[0]){
                res = max(res, dfs(c, t, z+1));
            }
        }
    }
    if(e && z%2){
        res = 1;
    }
    return res;
}

int main(){
    int n,m;
    cin>>n;
    vector<pair<vector<bool>, vector<int>>> t(1, {vector<bool>(2,1), vector<int>(26,-1)});
    string s;
    for(int i = 0; i<n; i++){
        cin>>s;
        insert(s,t, 0);
    }
    cin>>m;
    for(int i = 0; i<m; i++){
        cin>>s;
        insert(s, t, 1);
    }
    // for(auto e : t){
    //     for(auto ee : e.second){
    //         cout<<ee<<" ";
    //     }
    //     cout<<"\n";
    // }


    if(dfs(0,t,0) == 1){
        cout<<"Nina"<<"\n";
    }
    else{
        cout<<"Emilija"<<"\n";
    }
}
#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...