Submission #1311362

#TimeUsernameProblemLanguageResultExecution timeMemory
1311362forevpurityVlak (COCI20_vlak)C++20
70 / 70
13 ms14416 KiB
#include <bits/stdc++.h>
using namespace std;

// clang-format off
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
// clang-format on

const int ALPHA = 26;

struct Trie {
  struct Node {
    int child[ALPHA];
    bool b[2];
    Node() {
      fill(child, child + ALPHA, -1);
      fill(b, b + 2, false);
    }
    int& operator[](int c) { return child[c]; }
  };

  vector<Node> nodes;

  Trie() { nodes.emplace_back(); }

  void add(const string& s, int id) {
    int at = 0;
    for (char ch : s) {
      int c = ch - 'a';
      if (nodes[at][c] == -1) {
        nodes[at][c] = size(nodes);
        nodes.emplace_back();
      }
      at = nodes[at][c];
      nodes[at].b[id] = true;
    }
  }

  bool solve(int at, int id) {
    for (int i = 0; i < ALPHA; i++) {
      if (nodes[at][i] != -1) {
        int t = nodes[at][i];
        if (nodes[t].b[id] && !solve(t, id ^ 1)) { return true; }
      }
    }

    return false;
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  // 古力娜扎

  int TC = 1;
  for (int tc = 1; tc <= TC; tc++) {
    int n;
    cin >> n;
    string s;
    Trie tr;
    for (int i = 0; i < n; i++) {
      cin >> s;
      tr.add(s, 0);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
      cin >> s;
      tr.add(s, 1);
    }

    if (tr.solve(0, 0)) cout << "Nina";
    else cout << "Emilija";
  }

  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...