oj.uz

Submission #373534

# Submission time Handle Problem Language Result Execution time Memory
373534 2021-03-05T02:02:20 Z Scrubpai Vlak (COCI20_vlak) C++14
70 / 70
 299 ms 454636 KB 
#include <bits/stdc++.h>
using namespace std;

const int ABC = 28;
const int MAXN = 1000010;

struct Node {
  int state;
  Node *child[ABC];

  Node() {
    state = 0;
    for (int i=0; i<ABC; i++) child[i] = NULL;
  }
};

int cnt;
Node nodes[MAXN * 2];

Node *newNode() {
  return &nodes[cnt++];
}

struct Trie {
  Node *root;

  Trie() {
    root = newNode(); //points to the address of nodes[cnt]
  }

  void insert(Node *node, string &s, int pos, int mask) {
    if (pos == (int)s.size()) {
      return;
    }
    if (!node->child[s[pos] - 'a']) {
      node->child[s[pos] - 'a'] = newNode();
    }
    node->child[s[pos]-'a']->state |= mask;
    insert(node->child[s[pos] - 'a'], s, pos + 1, mask);
  }

  int solve(Node *node, int turn) {
    for (int i = 0; i < ABC; i++) {
      if (node->child[i] && (node->child[i]->state & (1<<turn)) && !solve(node->child[i], turn ^ 1)) {
        return 1;
      }
    }
    return 0;
  }
};

Trie T;

const string ans[] = {"Emilija", "Nina"};

int main() {
  for (int i = 0; i < 2; i++) {
    int n;
    string s;
    cin >> n;
    for (int j = 0; j < n; j++) {
      cin >> s;
      T.insert(T.root, s, 0, (1 << i));
    }
  }

  cout << ans[T.solve(T.root, 0)] << endl;

  /*
   * 1
bbb
2
bba
bbbb
   */
//lol nice solution fails that case
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 454380 KB Output is correct
2 Correct 265 ms 454380 KB Output is correct
3 Correct 267 ms 454412 KB Output is correct
4 Correct 273 ms 454380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 454380 KB Output is correct
2 Correct 277 ms 454380 KB Output is correct
3 Correct 271 ms 454528 KB Output is correct
4 Correct 264 ms 454636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 454380 KB Output is correct
2 Correct 266 ms 454324 KB Output is correct
3 Correct 265 ms 454380 KB Output is correct
4 Correct 264 ms 454380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 454380 KB Output is correct
2 Correct 265 ms 454380 KB Output is correct
3 Correct 266 ms 454380 KB Output is correct
4 Correct 267 ms 454380 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 454508 KB Output is correct
2 Correct 282 ms 454380 KB Output is correct
3 Correct 298 ms 454380 KB Output is correct
4 Correct 277 ms 454376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 454380 KB Output is correct
2 Correct 277 ms 454508 KB Output is correct
3 Correct 290 ms 454380 KB Output is correct
4 Correct 278 ms 454380 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 454508 KB Output is correct
2 Correct 299 ms 454380 KB Output is correct
3 Correct 279 ms 454380 KB Output is correct
4 Correct 275 ms 454392 KB Output is correct