Submission #1154020

#TimeUsernameProblemLanguageResultExecution timeMemory
1154020salmonVlak (COCI20_vlak)C++20
70 / 70
16 ms15400 KiB
#include <bits/stdc++.h>
using namespace std;

int N;
int M;
int lst[100100];
vector<int> b;
vector<string> v1;
vector<string> v2;
vector<pair<string,int>> v;
int has[200100];

map<int,int> adjlst[200100];
int cont = 0;


bool dfs(int i, int par){
    bool lose = true;
//printf("s");
    if( (has[i]&par) == 0 ) return !lose;
//printf("e");
    for(pair<int,int> ii : adjlst[i]){
        if( (has[ii.second]&par) > 0 ){
            //printf("%d %d\n",ii.first,ii.second);
            bool bol = dfs(ii.second, (3^par));
            //printf("%d\n",bol);
            lose &= bol;
        }
    }

    return !lose;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> N;

    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        v1.push_back(s);
        v.push_back({s,2});
    }

    sort(v1.begin(),v1.end());

    vector<int> tr = {};

    for(int i = 0; i < N; i++){
        tr.push_back(i);
    }

    cin >> M;

    for(int i = 0; i < M; i++){
        string s;
        cin >> s;
        v2.push_back(s);
        v.push_back({s,1});
    }

    cont = 1;

    has[0] = 0;

    for(int i = 0; i < N + M; i++){
        int in = 0;
        for(int j = 0; j < v[i].first.size(); j++){
            has[in] |= v[i].second;

            if(adjlst[in].find(v[i].first[j] - 'a') == adjlst[in].end() ){
                adjlst[in][v[i].first[j] - 'a'] = cont;
                in = cont;
                has[cont] = 0;
                cont++;
            }
            else{
                in = adjlst[in][v[i].first[j] - 'a'];
            }

            if(j == v[i].first.size() - 1){
                has[in] |= v[i].second;
            }
        }
    }


    if(!dfs(0,2)){
        printf("Emilija");
    }
    else{
        printf("Nina");
    }

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