Submission #1204425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204425		campos	Vlak (COCI20_vlak)	C++20	10 / 70	106 ms	211784 KiB

Main

#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 = 1e6;
int trie[MAXN][26][2];
int memo[MAXN][2];
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];
  }
}

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

  function<int(int,int,int)> dp = [&](int node1, int node2, int turn) {
    int &ans = memo[turn ? node1 : node2][turn];
    if(ans != -1) return ans;
    if(!turn) {
      ans = 0;
      for(int i = 0; i < 26; i++) {
        if(trie[node2][i][1] != -1) {
          if(trie[node1][i][0] == -1) return ans = 1;
          ans |= dp(trie[node1][i][0], trie[node2][i][1], 1);
        }
      }
    }
    else {
      ans = 1;
      for(int i = 0; i < 26; i++) {
        if(trie[node1][i][0] != -1) {
          if(trie[node2][i][1] == -1) return ans = 0;
          ans &= dp(trie[node1][i][0], trie[node2][i][1], 0);
        }
      }
    }
    return ans;
  };

  if(dp(0, 0, 0)) cout << "Nina" << "\n";
  else cout << "Emilija" << "\n";
  return 0;
}

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