Submission #1356385

#TimeUsernameProblemLanguageResultExecution timeMemory
1356385CutSandstoneVlak (COCI20_vlak)C++20
70 / 70
8 ms10012 KiB
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
using ll = long long;
const int N = 2e5;
int trie[N][26];
bool has1[N], has2[N];
bool turn[N];
bool win[N];
int ptr = 1;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	fill(trie[0], trie[0] + 26, -1);
	while (n--) {
		string s;
		cin >> s;
		int p = 0;
		for (char c : s) {
			int d = c - 'a';
			if (trie[p][d] == -1) {
				fill(trie[ptr], trie[ptr] + 26, -1);
				turn[ptr] = !turn[p];
				trie[p][d] = ptr++;
			}
			p = trie[p][d];
			has1[p] = 1;
		}
	}
	int m;
	cin >> m;
	while (m--) {
		string s;
		cin >> s;
		int p = 0;
		for (char c : s) {
			int d = c - 'a';
			if (trie[p][d] == -1) {
				fill(trie[ptr], trie[ptr] + 26, -1);
				turn[ptr] = !turn[p];
				trie[p][d] = ptr++;
			}
			p = trie[p][d];
			has2[p] = 1;
		}
	}
	for (int i = ptr - 1; i >= 0; i--) {
		if (turn[i]) {
			win[i] = 0;
			for (int j = 0; j < 26; j++)
				if (trie[i][j] != -1 && has2[trie[i][j]] && win[trie[i][j]]) {
					win[i] = 1;
					break;
				}
		} else {
			win[i] = 1;
			for (int j = 0; j < 26; j++)
				if (trie[i][j] != -1 && has1[trie[i][j]] && !win[trie[i][j]]) {
					win[i] = 0;
					break;
				}
		}
	}
	cout << (win[0] ? "Emilija\n" : "Nina\n");
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...