Submission #1153826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153826		siewjh	Vlak (COCI20_vlak)	C++20	70 / 70	32 ms	37444 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
set<pair<int, int>> adj[3][MAXN];
int nodes = 1;
int dfs(int x, int p){
	int ans = 1 - p;
	for (auto &[ch, id] : adj[p][x]){
		if (adj[1 - p][x].count({ch, id})){
			int ca = dfs(id, 1 - p);
			if (ca == p){
				ans = p; break;
			}
		}
		else{
			ans = p; break;
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int p = 0; p <= 1; p++){
		int nums; cin >> nums;
		for (int i = 0; i < nums; i++){
			string str; cin >> str;
			int curr = 1;
			for (char ch : str){
				int x = ch - 'a';
				auto it = adj[2][curr].lower_bound({x, -1});
				if (it != adj[2][curr].end() && it->first == x){
					if (!adj[p][curr].count(*it)) adj[p][curr].insert(*it);
					curr = it->second;
				}
				else{
					nodes++;
					adj[p][curr].insert({x, nodes});
					adj[2][curr].insert({x, nodes});
					curr = nodes;
				}
			}
		}
	}
	cout << (dfs(1, 0) ? "Emilija" : "Nina");
}

• 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