Submission #1150418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150418		luishgh	Vlak (COCI20_vlak)	C++20	70 / 70	26 ms	22532 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int SIG = 26 + 1;

vector<string> d;

struct node {
  vector<int> to;
  vector<short> col;
  bool term;
  node(bool _term = false): term(_term) {
    to.assign(SIG, -1);
    col.assign(SIG, 0);
  }
};

struct trie {
  vector<node> t;
  vector<bool> vis;
  vector<bool> w[2]; // w[0][i] => i is winning for player 0, if 0 starts
  int idx = 0;

  trie() {
    t.push_back(node());
    idx++;
  }

  void insert(const string& s, int p) {
    int i = 0;
    for (char c : s) {
      t[i].col[c-'a'] |= (1 << p);
      if (t[i].to[c-'a'] != -1) {
        i = t[i].to[c-'a'];
        continue;
      }
      t.push_back(node());
      t[i].to[c-'a'] = idx;
      i = idx;
      idx++;
    }
    t[i].term = true;
  }

  int go(int i, char cc) {
    int c = cc - 'a';
    return t[i].to[c];
  }

  void dfs(int v) {
    // 0 starts:
    if (vis[v]) return;
    for (int p = 0; p < 2; p++) {
      int op = p ^ 1;
      // w[p][v] = false;
      for (int c = 0; c < SIG; c++) {
        if (!(t[v].col[c] & (1 << p))) continue;
        int ww = t[v].to[c];
        dfs(ww);
        w[p][v] = w[p][v] or !w[op][ww];
      }
    }
    vis[v] = true;
  }
};

int main() {_
    struct trie t;

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

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

  t.w[0].assign(t.idx, false);
  t.w[1].assign(t.idx, false);
  t.vis.assign(t.idx, false);
  t.dfs(0);

  if (t.w[0][0]) cout << "Nina" << endl;
  else cout << "Emilija" << endl;

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10