Submission #1204440

#TimeUsernameProblemLanguageResultExecution timeMemory
1204440camposVlak (COCI20_vlak)C++20
0 / 70
185 ms415304 KiB
#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 = 2e6;
int trie[MAXN][26][2];
int memo[MAXN];
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 and i == -1) return 0;
  if(turn and j == -1) return 1;
  if(memo[i] != -1) return memo[i];
  memo[i] = turn;
  for(int k = 0; k < 26; k++) {
    if(trie[(turn ? j : i)][k][turn] == -1) continue;
    if(!turn) memo[i] |= dp(trie[i][k][0], trie[j][k][1], 1);
    else memo[i] &= dp(trie[i][k][0], trie[j][k][1], 1);
  }
  return memo[i];
}

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