Submission #1204434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204434		campos	Vlak (COCI20_vlak)	C++20	In queue	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

/*
 * LE O PROBLEMA ATE O FINAL
 * LE OS SAMPLES, ENTENDE OS SAMPLES
 * LE INPUT, LE OUTPUT
 * LE OS CONSTRAINTS
 */

const int MAXN = 1e6;
int trie[MAXN][26][2];
int memo[MAXN][2];
int id[2];

void insert(string &s, int who) {
  int node = 0;
  for(int i = 0; i < (int)s.size(); i++) {
    int c = s[i] - 'a';
    if(trie[node][c][who] == -1) trie[node][c][who] = ++id[who];
    node = trie[node][c][who];
  }
}

int dp(int i, int j, int turn) {
  if(!turn) {
    if(i == -1) return 0;
    if(memo[i][turn] != -1) return memo[i][turn];
    memo[i][turn] = 0;
    for(int k = 0; k < 26; k++) {
      if(trie[i][k][0] == -1) continue;
      memo[i][turn] |= dp(trie[i][k][1], trie[j][k][0], 1);
    }
  }
  else {
    if(j == -1) return 1;
    if(memo[i][turn] != -1) return memo[i][turn];
    memo[i][turn] = 1;
    for(int k = 0; k < 26; k++) {
      if(trie[j][k][1] == -1) continue;
      memo[i][turn] &= dp(trie[i][k][1], trie[j][k][0], 0);
    }
  }
  return memo[i][turn];
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  memset(trie, -1, sizeof trie);
  memset(memo, -1, sizeof memo);

  int n, m; string word;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> word;
    insert(word, 0);
  }
  cin >> m;
  for(int i = 0; i < m; i++) {
    cin >> word;
    insert(word, 1);
  }

  if(dp(0, 0, 0)) cout << "Nina" << "\n";
  else cout << "Emilija" << "\n";
  return 0;
}