제출 #1336778

#제출 시각아이디문제언어결과실행 시간메모리
1336778iamsazidhVlak (COCI20_vlak)C++20
70 / 70
14 ms15296 KiB
//Code by ChatGPT
#include <bits/stdc++.h>
using namespace std;

struct Trie {
    vector<array<int,26>> nxt;
    Trie() { nxt.push_back({}); }

    int add_node() {
        nxt.push_back({});
        nxt.back().fill(-1);
        return nxt.size()-1;
    }

    void insert(string s) {
        int u = 0;
        for(char c : s) {
            int x = c-'a';
            if(nxt[u][x] == -1) {
                nxt[u][x] = add_node();
            }
            u = nxt[u][x];
        }
    }
};

Trie A,B;

unordered_map<long long,bool> memo;

bool dfs(int u,int v,int turn){

    if(turn==0 && u==-1) return false;
    if(turn==1 && v==-1) return false;

    long long key = ((long long)(u+2)<<33) | ((long long)(v+2)<<1) | turn;

    if(memo.count(key)) return memo[key];

    if(turn==0){
        bool can=false;

        for(int c=0;c<26;c++){
            int nu = (u==-1?-1:A.nxt[u][c]);
            if(nu==-1) continue;

            can=true;

            int nv = -1;
            if(v!=-1) nv = B.nxt[v][c];

            if(!dfs(nu,nv,1))
                return memo[key]=true;
        }

        if(!can) return memo[key]=false;
        return memo[key]=false;
    }

    else{

        bool can=false;

        for(int c=0;c<26;c++){
            int nv = (v==-1?-1:B.nxt[v][c]);
            if(nv==-1) continue;

            can=true;

            int nu = -1;
            if(u!=-1) nu = A.nxt[u][c];

            if(!dfs(nu,nv,0))
                return memo[key]=true;
        }

        if(!can) return memo[key]=false;
        return memo[key]=false;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    A.nxt[0].fill(-1);
    B.nxt[0].fill(-1);

    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        A.insert(s);
    }

    int m;
    cin>>m;

    for(int i=0;i<m;i++){
        string s;
        cin>>s;
        B.insert(s);
    }

    bool win = dfs(0,0,0);

    if(win) 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...