Submission #1154426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154426		gelastropod	Vlak (COCI20_vlak)	C++20	70 / 70	47 ms	31448 KiB

Main

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

vector<vector<int>> adjlist;
vector<int> depth;
vector<bool> hasN, hasE;
vector<bool> win;

bool dfs(int n) {
	bool mt = true;
	for (int i : adjlist[n])
		if (i != -1)
			mt = false;
	if (mt)
		return win[n] = (depth[n] % 2 ? hasN[n] : !hasE[n]);
	bool cwin = (depth[n] % 2);
	for (int i : adjlist[n]) {
		if (i != -1) {
			depth[i] = depth[n] + 1;
			bool winn = dfs(i);
			if (!(depth[n] % 2)) {
				cwin = cwin || winn;
			}
			else {
				cwin = cwin && winn;
			}
		}
	}
	return win[n] = cwin;
}

signed main() {
	int n, m;
	string s;
	int count = 0;
	adjlist.push_back(vector<int>(26, -1));
	hasN.push_back(true);
	hasE.push_back(true);
	vector<string> strings;
	strings.push_back("");
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		int crnt = 0;
		for (int j = 0; j < s.size(); j++) {
			if (adjlist[crnt][s[j] - 'a'] == -1) {
				adjlist.push_back(vector<int>(26, -1));
				crnt = adjlist[crnt][s[j] - 'a'] = ++count;
				hasN.push_back(true);
				hasE.push_back(false);
				strings.push_back(s.substr(0, j + 1));
			}
			else {
				crnt = adjlist[crnt][s[j] - 'a'];
			}
		}
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s;
		int crnt = 0;
		for (int j = 0; j < s.size(); j++) {
			if (adjlist[crnt][s[j] - 'a'] == -1) {
				adjlist.push_back(vector<int>(26, -1));
				crnt = adjlist[crnt][s[j] - 'a'] = ++count;
				hasE.push_back(true);
				hasN.push_back(false);
				strings.push_back(s.substr(0, j + 1));
			}
			else {
				hasE[crnt] = true;
				crnt = adjlist[crnt][s[j] - 'a'];
			}
		}
		hasE[crnt] = true;
	}
	depth = vector<int>(count + 1, 0);
	win = vector<bool>(count + 1, false);
	cout << (dfs(0) ? "Nina" : "Emilija") << '\n';
}

• 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