Submission #370027

#	Time	Username	Problem	Language	Result	Execution time	Memory
370027		penguinhacker	Vlak (COCI20_vlak)	C++14	70 / 70	58 ms	15752 KiB

Main

// source: https://oj.uz/problem/view/COCI20_vlak
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int ALP=26;
struct Node {
	int nxt[ALP];
	Node() {fill(nxt, nxt+ALP, -1);}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void add(string s) {
		int cur=0;
		for (char ch: s) {
			int c=ch-'a';
			if (trie[cur].nxt[c]==-1) {
				trie[cur].nxt[c]=trie.size();
				trie.emplace_back();
			}
			cur=trie[cur].nxt[c];
		}
	}
} t1, t2;

bool solve(int p1, int p2, Trie& x, Trie& y) {
	for (int i = 0; i < 26; ++i) {
		if (x.trie[p1].nxt[i] != -1) {
			if (y.trie[p2].nxt[i] == -1) return 1;
			if (!solve(y.trie[p2].nxt[i], x.trie[p1].nxt[i], y, x)) return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	while(n--) {
		string s; cin >> s;
		t1.add(s);
	}
	cin >> n;
	while(n--) {
		string s; cin >> s;
		t2.add(s);
	}
	cout << (solve(0, 0, t1, t2) ? "Nina" : "Emilija") << "\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