oj.uz

Submission #1084764

# Submission time Handle Problem Language Result Execution time Memory
1084764 2024-09-06T23:47:18 Z Hamed5001 Vlak (COCI20_vlak) C++14
70 / 70
 12 ms 21000 KB 
#include <bits/stdc++.h>

using namespace std;

const int mxM = 2e5 + 1;

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

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

bool dfs(array<int, 2> v, int which) {
  bool ret = 0;
  for (int i = 0; i < 26; ++i) {
    if (trie[v[which]][i][which]) {
      if (!trie[v[1-which]][i][1-which]) {
        return 1;
      }
      ret |= !dfs({trie[v[0]][i][0], trie[v[1]][i][1]}, 1 - which);
    }
  }
  return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    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);
    }
    cout << (dfs({0, 0}, 0) ? "Nina" : "Emilija");
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19544 KB Output is correct
2 Correct 10 ms 18268 KB Output is correct
3 Correct 9 ms 17240 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19804 KB Output is correct
2 Correct 12 ms 21000 KB Output is correct
3 Correct 10 ms 19292 KB Output is correct
4 Correct 11 ms 19328 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18780 KB Output is correct
2 Correct 11 ms 18264 KB Output is correct
3 Correct 11 ms 18696 KB Output is correct
4 Correct 11 ms 20060 KB Output is correct