제출 #1084763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084763		Hamed5001	Vlak (COCI20_vlak)	C++14	70 / 70	16 ms	22156 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int mxM = 2e5 + 1;

int trie[mxM][26][2], last, out[mxM];
int dp[mxM];

void insert(string const &s, int which) {
  int v = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[v][c][which]) 
      trie[v][c][which] = ++last;
    v = trie[v][c][which];
  }
  out[v]++;
}

void dfs(array<int, 2> v, int which) {
  auto &ret = dp[v[which]];
  if (~ret) return;
  ret = 0;
  for (int i = 0; i < 26; ++i) {
    if (trie[v[which]][i][which]) {
      if (!trie[v[1-which]][i][1-which]) {
        ret = true;
        break;
      }
      dfs({trie[v[0]][i][0], trie[v[1]][i][1]}, 1 - which);
      ret |= !dp[trie[v[1-which]][i][1-which]];
    }
  }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    memset(dp, -1, sizeof dp);
    int N; cin >> N;
    for (int i = 0; i < N; ++i) {
      string s; cin >> s;
      insert(s, 0);
    }
    cin >> N;
    for (int i = 0; i < N; ++i) {
      string s; cin >> s;
      insert(s, 1);
    }
    dfs({0, 0}, 0);
    cout << (dp[0] ? "Nina" : "Emilija");
    return 0;
}

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