Submission #1271769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271769		cbnk32_tuandung	Vlak (COCI20_vlak)	C++17	70 / 70	14 ms	21064 KiB

Main

#include <bits/stdc++.h>
using namespace std;

// quy uoc 0: Nina
//         1: Emilija

int n,m;
int trie[200009][26][2];
int nTrie=0;
bool xd[200009][2];
bool L[200009][2];
string tmp;

void addTrie(bool mask, string s) {
	int u = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (!trie[u][s[i]-'a'][mask]) trie[u][s[i]-'a'][mask] = ++nTrie;
		u = trie[u][s[i]-'a'][mask];
	}
}

bool dequy(bool mask, int u1, int u2) {
	int u = mask ? u2 : u1;
	if (xd[u][mask]) return L[u][mask];
	xd[u][mask]=true; bool best=false;
	for (int i = 0; i < 26; ++i) {
		if (trie[u][i][mask]) {
			int u11 = trie[u1][i][0];
			int u22 = trie[u2][i][1];
			if ((!u11) || (!u22)) {
				best = true;
				break;
			}
			best = best || (!(dequy(!mask,u11,u22)));
		}
	}
	return (L[u][mask]=best);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> tmp;
		addTrie(0,tmp);
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> tmp;
		addTrie(1,tmp);
	}
	if (dequy(0,0,0)) cout << "Nina";
	else cout << "Emilija";
}

• 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