Submission #1162233

#TimeUsernameProblemLanguageResultExecution timeMemory
1162233alorivaldoVlak (COCI20_vlak)C++20
0 / 70
16 ms23616 KiB
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;

#define br '\n'

class Trie{
public:
  bool a;
  bool b;
  vector<Trie*> children;

  Trie(){
    a = b = false;
    children.resize(26);
    for (int i = 0; i < 26; i++){
      children[i] = nullptr;
    }
  }
};

void add(Trie* T, string& s, int pos, bool isa){
  if (isa) T->a = true;
  else T->b = true;

  char c = s[pos]-'a';

  if (T->children[c] == nullptr){
    T->children[c] = new Trie;
  }

  if (pos < s.size()-1){
    add(T->children[c], s, pos+1, isa);
  }
}

// emilija wins?
bool check(Trie* root, string& str)
{
  Trie* cur = root->children[str[0]-'a'];
  int n = str.size();
  
  for (int i = 0; i < n; i++){

    // ver se b morreu
    if (!cur->b) return false;

    // par e 01
    if ((i&1)==0){
      for (int j = 0; j < 26; j++){
        if (cur->children[j] != nullptr && !(cur->children[j]->a) && cur->children[j]->b){
          return true;
        }
      }
    }

    // impar, b chegou até aqui e 'a' acabou
    else {
      if (i == n-1) return true;
    }
    
    if (i < n-1) cur = cur->children[str[i]-'a'];
  }


  return false;
}


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  vector<string> N;
  string s;
  int n,m;
  cin>>n;

  Trie root;

  for (int i = 0; i < n; i++){
    cin>>s;
    add(&root,s,0,1);
    N.push_back(s);
  }
  cin>>m;
  for (int i = 0; i < m; i++){
    cin>>s;
    add(&root,s,0,0);
  }

  bool emilija = true;
  for (string str: N){
    emilija = emilija && check(&root,str);
  }
  cout << (emilija ? "Emilija" : "Nina") << br;


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