oj.uz

Submission #474486

# Submission time Handle Problem Language Result Execution time Memory
474486 2021-09-18T12:27:04 Z arnavt Vlak (COCI20_vlak) C++17
70 / 70
 24 ms 21284 KB 
#include <bits/stdc++.h>
using namespace std;

// Debugging
#define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl;

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

const int MAXN = 2e5 + 10, MAXC = 26;

struct Trie {
  int trie[MAXN][MAXC];
  bool data[MAXN][2];
  int size = 1;

  Trie() {
    memset(trie, -1, sizeof(trie));
    memset(data, 0, sizeof(data));
  }

  void insert(const string& s, int d) {
    int i = 0;
    for (char c : s) {
      int ch = c-'a';
      if (trie[i][ch] == -1) trie[i][ch] = size++;
      data[i][d] = 1;
      i = trie[i][ch];
    }
  }

  int dfs(int i = 0, int d = 0) {
    for (int ch=0; ch<MAXC; ++ch) {
      if (trie[i][ch] == -1) continue;
      if (!data[i][d]) continue;
      if (!data[i][d^1]) return d;
      if (dfs(trie[i][ch], d^1) == d) return d;
    }
    return d^1;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  Trie t;
  string s;
  int n, m;
  cin >> n;
  while (n--) {
    cin >> s;
    t.insert(s, 0);
  }
  cin >> m;
  while (m--) {
    cin >> s;
    t.insert(s, 1);
  }

  if (t.dfs() == 0) cout << "Nina\n";
  else cout << "Emilija\n";

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20952 KB Output is correct
2 Correct 16 ms 21056 KB Output is correct
3 Correct 17 ms 21052 KB Output is correct
4 Correct 14 ms 21048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20940 KB Output is correct
2 Correct 17 ms 21032 KB Output is correct
3 Correct 13 ms 20940 KB Output is correct
4 Correct 14 ms 20940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21048 KB Output is correct
2 Correct 15 ms 20996 KB Output is correct
3 Correct 14 ms 21048 KB Output is correct
4 Correct 16 ms 21052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20940 KB Output is correct
2 Correct 15 ms 21056 KB Output is correct
3 Correct 16 ms 21052 KB Output is correct
4 Correct 18 ms 21048 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21196 KB Output is correct
2 Correct 22 ms 21164 KB Output is correct
3 Correct 20 ms 21188 KB Output is correct
4 Correct 21 ms 21256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21276 KB Output is correct
2 Correct 19 ms 21140 KB Output is correct
3 Correct 19 ms 21196 KB Output is correct
4 Correct 24 ms 21132 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21196 KB Output is correct
2 Correct 19 ms 21196 KB Output is correct
3 Correct 24 ms 21284 KB Output is correct
4 Correct 21 ms 21196 KB Output is correct