제출 #1287087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287087		muhammadali_2009	Vlak (COCI20_vlak)	C++17	0 / 70	354 ms	532740 KiB

Main

// +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+ // 
#include <bits/stdc++.h> 
//#include<ext/pb_ds/assoc_container.hpp> 
//#include<ext/pb_ds/tree_policy.hpp> 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) 
#define endl '\n' 
#define ll long long 
#define int long long 
#define all(x) x.begin(), x.end() 
#define all1(x) x.rbegin(), x.rend() 
#define seea(x) for(int i = 0; i < x; i++) 
#define pb push_back 
#define ff first 
#define vc vector 
#define ss second 
#define ld long double 

using namespace std; 
const int mod = 1e9 + 7; 

const int mxn = 1000002; // kept as in official
vector<vector<int>> tr1(mxn, vc<int>(26, 0)), tr2(mxn, vc<int>(26, 0));
int cnt1 = 0, cnt2 = 0;
vc<int> stop1(mxn, 0), stop2(mxn, 0);

vc<int> lvl(mxn, 0);
vc<int> cntA(mxn, 0), cntB(mxn, 0);
vc<int> f(mxn, -1);

void insert(string a){
    int cur = 0;
    cntA[0]++;
    for(char c : a){
        int id = c - 'a';
        if(tr1[cur][id] == 0){
            ++cnt1;
            tr1[cur][id] = cnt1;
            lvl[cnt1] = lvl[cur] + 1;
        }
        cur = tr1[cur][id];
        cntA[cur]++;
    }
    stop1[cur] = 1;
}

void insert2(string a){
    int cur = 0;
    cntB[0]++;
    for(char c : a){
        int id = c - 'a';
        if(tr1[cur][id] == 0){
            ++cnt1;
            tr1[cur][id] = cnt1;
            lvl[cnt1] = lvl[cur] + 1;
        }
        cur = tr1[cur][id];
        cntB[cur]++;
    }
    stop2[cur] = 1;
}

int dp(int node){
    if(f[node] != -1) return f[node];
    int turn = lvl[node] & 1; // 0 -> Nina to move, 1 -> Emilija to move

    f[node] = 0;
    if(turn == 0){
        if(!cntA[node]) return f[node] = 0;
    } else {
        if(!cntB[node]) return f[node] = 0;
    }

    for(int c = 0; c < 26; ++c){
        int childPos = tr1[node][c];
        if(childPos == 0) continue;
        if(dp(childPos) == 0){
            f[node] = 1;
            break;
        }
    }
    return f[node];
}

void solve(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        insert(s);
    }
    int m; cin >> m;
    for(int i = 0; i < m; i++){
        string s; cin >> s;
        insert2(s);
    }
    for(int i = 0; i <= cnt1; ++i) f[i] = -1;
    cout << (dp(0) ? "Nina\n" : "Emilija\n");
}

signed main(){ 
    fast; 
    int t = 1; 
    while (t --){ 
        solve(); 
    } 
    return 0; 
}

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