Submission #1320445

#TimeUsernameProblemLanguageResultExecution timeMemory
1320445a.pendovVlak (COCI20_vlak)C++20
70 / 70
18 ms21412 KiB
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=300009,MAXL=26;
long long trie[MAXN][MAXL];
bool pref[MAXN][2];
int dp[MAXN][2];
int currNodes=0;

void insertWord(string a,bool p)
{
    int node=0;
    for(auto i:a)
    {
        pref[node][p]=1;
        if(trie[node][i-'a']==0)
        {
            trie[node][i-'a']=++currNodes;
            //cout<<node<<" "<<i-'a'<<" "<<currNodes<<endl;
        }
        node=trie[node][i-'a'];
    }
    pref[node][p]=1;
}

bool f(int n,int p)
{
    if(dp[n][p]!=-1)return dp[n][p];
    dp[n][p]=0;
    for(int i=0;i<MAXL;i++)
    {
        if(trie[n][i]==0)continue;
        dp[n][p]=dp[n][p]||(pref[trie[n][i]][p]&&(!f(trie[n][i],1-p)));
    }
    //cout<<n<<" "<<p<<" "<<dp[n][p]<<endl;
    return dp[n][p];
}

signed main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long N;
    memset(dp,-1,sizeof(dp));
    string a;
    cin>>N;
    while(N--)
    {
        cin>>a;
        insertWord(a,0);
    }

    cin>>N;
    while(N--)
    {
        cin>>a;
        insertWord(a,1);
    }

    //cout<<"    "<<pref[6][1]<<endl;
    //cout<<f(6,1)<<endl<<f(5,0)<<endl<<f(4,1)<<endl<<f(0,0)<<endl;

    if(f(0,0))cout<<"Nina"<<endl;
    else cout<<"Emilija"<<endl;

    return 0;
}
#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...