oj.uz

Submission #1084763

# Submission time Handle Problem Language Result Execution time Memory
1084763 2024-09-06T23:44:43 Z Hamed5001 Vlak (COCI20_vlak) C++14
70 / 70
 16 ms 22156 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20828 KB Output is correct
2 Correct 13 ms 19660 KB Output is correct
3 Correct 13 ms 18520 KB Output is correct
4 Correct 12 ms 20332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21340 KB Output is correct
2 Correct 13 ms 22156 KB Output is correct
3 Correct 10 ms 20572 KB Output is correct
4 Correct 12 ms 20828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20060 KB Output is correct
2 Correct 11 ms 19620 KB Output is correct
3 Correct 11 ms 20060 KB Output is correct
4 Correct 12 ms 21444 KB Output is correct