oj.uz

Submission #953521

# Submission time Handle Problem Language Result Execution time Memory
953521 2024-03-26T05:07:55 Z DarkKnight101 Vlak (COCI20_vlak) C++17
70 / 70
 218 ms 454480 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

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

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

  Node() {
    state = 0;
    REP(i, ABC) child[i] = NULL;
  }
};

int cnt;
Node nodes[MAXN * 2];

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

struct Trie {
  Node *root;

  Trie() {
    root = newNode();
  }

  void insert(Node *node, string &s, int mask) {
    Node* temp = node;
    int n = s.length();
    for(int i=0;i<n;i++){
      temp->state|=mask;
      if (!temp->child[s[i] - 'a']) {
        temp->child[s[i] - 'a'] = newNode();
      }
      temp = temp->child[s[i]-'a'];

    }
  }

  int solve(Node *node, int turn) {
    if (!(node->state & (1 << turn))) {
      return 0;
    }

    for (int i = 0; i < ABC; i++) {
      if (node->child[i] && !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, (1 << i));
    }
  }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 454364 KB Output is correct
2 Correct 142 ms 454192 KB Output is correct
3 Correct 148 ms 454220 KB Output is correct
4 Correct 142 ms 454228 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 454428 KB Output is correct
2 Correct 142 ms 454436 KB Output is correct
3 Correct 146 ms 454388 KB Output is correct
4 Correct 143 ms 454408 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 454404 KB Output is correct
2 Correct 142 ms 454324 KB Output is correct
3 Correct 143 ms 454228 KB Output is correct
4 Correct 149 ms 454296 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 454232 KB Output is correct
2 Correct 159 ms 454188 KB Output is correct
3 Correct 155 ms 454224 KB Output is correct
4 Correct 146 ms 454196 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 454236 KB Output is correct
2 Correct 150 ms 454224 KB Output is correct
3 Correct 151 ms 454256 KB Output is correct
4 Correct 151 ms 454324 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 454240 KB Output is correct
2 Correct 150 ms 454184 KB Output is correct
3 Correct 151 ms 454480 KB Output is correct
4 Correct 150 ms 454224 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 454412 KB Output is correct
2 Correct 150 ms 454224 KB Output is correct
3 Correct 150 ms 454224 KB Output is correct
4 Correct 149 ms 454228 KB Output is correct