Submission #474486

#TimeUsernameProblemLanguageResultExecution timeMemory
474486arnavtVlak (COCI20_vlak)C++17
70 / 70
24 ms21284 KiB
#include <bits/stdc++.h>
using namespace std;

// Debugging
#define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl;

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

const int MAXN = 2e5 + 10, MAXC = 26;

struct Trie {
  int trie[MAXN][MAXC];
  bool data[MAXN][2];
  int size = 1;

  Trie() {
    memset(trie, -1, sizeof(trie));
    memset(data, 0, sizeof(data));
  }

  void insert(const string& s, int d) {
    int i = 0;
    for (char c : s) {
      int ch = c-'a';
      if (trie[i][ch] == -1) trie[i][ch] = size++;
      data[i][d] = 1;
      i = trie[i][ch];
    }
  }

  int dfs(int i = 0, int d = 0) {
    for (int ch=0; ch<MAXC; ++ch) {
      if (trie[i][ch] == -1) continue;
      if (!data[i][d]) continue;
      if (!data[i][d^1]) return d;
      if (dfs(trie[i][ch], d^1) == d) return d;
    }
    return d^1;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  Trie t;
  string s;
  int n, m;
  cin >> n;
  while (n--) {
    cin >> s;
    t.insert(s, 0);
  }
  cin >> m;
  while (m--) {
    cin >> s;
    t.insert(s, 1);
  }

  if (t.dfs() == 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...