Submission #1154119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154119		gelastropod	Vlak (COCI20_vlak)	C++20	0 / 70	464 ms	589824 KiB

Main

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

bool comp(pair<string, int> a, pair<string, int> b) {
	if (a.first.size() == b.first.size()) return a.first < b.first;
	return a.first.size() < b.first.size();
}

vector<vector<int>> adjlist;
vector<int> depth;
vector<pair<string, int>> hahah;

bool dfs(int n) {
	if (adjlist[n].empty()) {
		if (depth[n] % 2) {
			if (hahah[n].second % 2) {
				return true;
			}
			else {
				return false;
			}
		}
		else {
			if (hahah[n].second & 2) {
				return false;
			}
			else {
				return true;
			}
		}
	}
	bool cwin = !(depth[n] % 2);
	for (int i : adjlist[n]) {
		depth[i] = depth[n] + 1;
		bool win = dfs(i);
		if (depth[n] % 2) {
			cwin = cwin || win;
		}
		else {
			cwin = cwin && win;
		}
	}
}

set<string> vals;

signed main() {
	int n, m;
	string s;
	cin >> n;
	set<string> sN, sM;
	for (int i = 0; i < n; i++) {
		cin >> s;
		sN.insert(s);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s;
		sM.insert(s);
	}
	for (string i : sN) {
		for (int j = 0; j < i.size(); j++) {
			vals.insert(i.substr(0, j + 1));
		}
	}
	for (string i : sM) {
		for (int j = 0; j < i.size(); j++) {
			vals.insert(i.substr(0, j + 1));
		}
	}
	hahah.push_back({ "", 3 });
	for (string i : vals) {
		hahah.push_back({ i, 0 });
		auto iter1 = sN.lower_bound(i);
		if (iter1 != sN.end() && *iter1 == i) {
			hahah.back().second += 1;
		}
		auto iter2 = sM.lower_bound(i);
		if (iter2 != sM.end() && *iter2 == i) {
			hahah.back().second += 2;
		}
	}
	sort(hahah.begin(), hahah.end(), comp);
	adjlist = vector<vector<int>>(hahah.size() + 1, vector<int>());
	vector<int> groups, prevgroups;
	prevgroups.push_back(0);
	int count = 1;
	int ind = 1;
	for (int siz = 0; ; siz++) {
		while (count < hahah.size() && hahah[count].first.size() == siz + 1) {
			groups.push_back(count);
			count++;
		}
		for (int i : prevgroups) {
			while (ind <= groups.back() && hahah[ind].first.substr(0, hahah[ind].first.size() - 1) == hahah[i].first) {
				adjlist[i].push_back(ind);
				ind++;
			}
		}
		prevgroups = groups;
		groups.clear();
		if (count == hahah.size()) break;
	}
	depth = vector<int>(hahah.size(), -1);
	depth[0] = 0;
	cout << (dfs(0) ? "Nina" : "Emilija") << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'bool dfs(long long int)':
Main.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10