Submission #670517

#	Time	Username	Problem	Language	Result	Execution time	Memory
670517		gokussjz	Vlak (COCI20_vlak)	C++17	70 / 70	15 ms	23208 KiB

Main

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;

const int MAX_NODES = 2e5 + 10;
const int MAX_ASCII_CODE = 26;
struct trie {
	int child[MAX_NODES][MAX_ASCII_CODE], tot, leaves[MAX_NODES], cnt[MAX_NODES][2];
	trie() {
		memset(child, -1, sizeof child);
		memset(leaves, 0, sizeof leaves);
		memset(cnt, 0, sizeof cnt);
		tot = 1;
	}
	void add(const string &s, const int msk) {
		int node = 0;
		for (const auto &ch : s) {
			int c = ch - 'a';
			if (child[node][c] == -1) child[node][c] = tot++;
			node = child[node][c];
			cnt[node][msk]++;
		}
		leaves[node]++;
	}

	bool search(const string &s) {
		int node = 0;
		for (const auto &ch : s) {
			int c = ch - 'a';
			if (child[node][c] == -1) return 0;
			node = child[node][c];
		}
		return leaves[node];
	}

	void reset() {
		memset(child, 0, sizeof(child[0]) * tot);
		memset(leaves, 0, sizeof(leaves[0]) * tot);
		tot = 1;
	}
} tr;

void solve() {
	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		tr.add(s, 0);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		tr.add(s, 1);
	}

	function<bool(int, int)> dfs = [&](int u, int depth) {
		bool ok = 0;
		for (int i = 0; i < 26; i++) {
			int curr = tr.child[u][i];
			if (curr != -1 && tr.cnt[curr][(depth & 1)]) {
				ok |= !dfs(curr, depth + 1);
			}
			if (ok) break;
		}
		return ok;
	};
	cout << (dfs(0, 0) ? "Nina" : "Emilija");
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
	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