Submission #1168425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168425		nuutsnoynton	Vlak (COCI20_vlak)	C++20	70 / 70	32 ms	44868 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll M = 1e6 + 1;
ll type, node_count = 0;;
ll trie[M][26], turul[M];
vector < ll > adj[M];
ll cnt[3][M];
void add_string(string str) {
	ll node = 0;
	for ( char ch : str) {
		if ( trie[node][ch - 'a'] == 0) trie[node][ch-'a'] = ++node_count;
		node = trie[node][ch - 'a'];
		cnt[type][node] = 1;
	}
}
ll Find(ll node) {
	ll neg, teg;
	neg = teg = 0;
	for( ll chi : adj[node]) {
		//cout << node << " "<< chi << " " << Find(chi) << " " << turul[chi]<< endl;
		if ( Find(chi) == 0) teg ++;
		else neg ++;
	}
	if ( neg + teg == 0) {
		return turul[node];
	}
	if ( turul[node] == 0) {
		if ( neg == 0) return 0;
		else return 1;
	}
	else {
		if ( teg== 0) return 1;
		else return 0;
	}
	
}
int main() {
	ll n, m, r, x,p, y, i, j,s, ans, t;

	cin >> n;
	
	
	string str1[n + 2];
	type = 1;
	for (i = 0; i < n; i ++) {
		cin >> str1[i];
		add_string(str1[i]);
	}
	cin >> m;
	type = 2;
	string str2[m + 2];
	for (i = 0; i < m; i ++) {
		cin >> str2[i];
		add_string(str2[i]);
	}
	
	queue < ll > q, v;
	q.push(0);
	type = 1;
	while (1) {
		while(!q.empty()) {
			r = q.front();
			q.pop();
			for (j = 0; j < 26; j ++) {
				p = trie[r][j];
				if (p == 0) continue;
				if (cnt[type][p] != 0) {
					turul[p] = 1 - turul[r]; 
					adj[r].push_back(p);
					v.push(p);
				}
			}
		}
		if ( v.empty()) break;
		swap(v, q);
		type = 3 - type;
	}
	if (Find(0)) cout << "Nina" << endl;
	else cout << "Emilija" << endl;
}

• 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