제출 #1274168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274168		dhuyyyy	Vlak (COCI20_vlak)	C++20	40 / 70	15 ms	23144 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,4>;

const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 998244353;  

int n, m, u, timer = 0;

int trie[2][N][27], dp[N];

string s;

void add(string s,int type){
    u = 0;
    for (char c : s){
        if (trie[type][u][c - 'a'] == 0) trie[type][u][c - 'a'] = ++timer;
        u = trie[type][u][c - 'a'];
    }
}
int dfs(int u,int v, int turn){ // u là trie 0, v là trie 1, turn là lượt
    if (dp[u] != -1) return dp[u];
    if (turn == 0){
        for (int j = 0; j <= 25; j++){
            if (trie[0][u][j] && !trie[1][v][j]){
                dp[u] = 0;
                return dp[u];
            }
        }
        for (int j = 0; j <= 25; j++){
            if (trie[0][u][j]){
                int tmp = dfs(trie[0][u][j],trie[1][v][j],1);
                if (tmp == 0){
                    dp[u] = tmp;
                    return dp[u];
                } else dp[u] = tmp;
            }
        }
    } else{
        for (int j = 0; j <= 25; j++){
            if (trie[0][u][j] && !trie[1][v][j]){
                dp[u] = 1;
                return dp[u];
            }
        }
        for (int j = 0; j <= 25; j++){
            if (trie[1][v][j]){
                int tmp = dfs(trie[0][u][j],trie[1][v][j],0);
                if (tmp == 1){
                    dp[u] = tmp;
                    return dp[u];
                } else dp[u] = tmp;
            }
        }
    }
    return dp[u];
}
signed main()
{   
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s;
        add(s,0);
    }    
    cin >> m;
    timer = 0;
    for (int i = 1; i <= m; i++){
        cin >> s;
        add(s,1);
    }
    for (int i = 0; i < 200000; i++) dp[i] = -1;
    cout << (dfs(0,0,0) == 0 ? "Nina" : "Emilija");
    return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10