Submission #1162263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162263		alorivaldo	Vlak (COCI20_vlak)	C++20	0 / 70	24 ms	23820 KiB

Main

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

  ~Trie() {  // Destructor to free memory
    for (Trie* child : children) {
      if (child) delete child;  // Recursively delete children
    }
  }

};

void add(Trie* T, string& s, int pos, bool isa){
  char c = s[pos]-'a';

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

  if (isa) T->children[c]->a = true;
  else T->children[c]->b = true;

  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 {
      // 'a' atual acabou
      if (i == n-1){
        // nenhuma outra string de nina tem prefixo que continua daqui
        bool some_a = false;
        for (int j = 0; j < 26; j++){
          if (cur->children[j] != nullptr && cur->children[j]->a) some_a = true;
        }
        if (!some_a) return true;
      }
    }
    
    if (i < n-1){
        cur = cur->children[str[i+1]-'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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10