Submission #450306

#	Time	Username	Problem	Language	Result	Execution time	Memory
450306		ArianKheirandish	Vlak (COCI20_vlak)	C++14	70 / 70	18 ms	11480 KiB

Main

//in the name of god//
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)			x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair
 
const int maxn = 2e5 + 10;
const int LG = 30;
const int Inf = 1e9 + 10;
int n, m, nw = 1;
int child[maxn][LG];
bool win[maxn], p[maxn][2];

void insert(int num, const string &s){
	int v = 1;
	for(char x : s){
		p[v][num] = 1;
		if(!child[v][x - 'a']) 
			v = child[v][x - 'a'] = ++ nw;
		else 
			v = child[v][x - 'a'];
	}
	p[v][num] = 1;
}
 
void dfs(int v = 1, int num = 1){
	bool lose = 0, barg = 1;
	for(int i = 0 ; i < 26 ; i ++){
		if(!child[v][i]) 
			continue;
		dfs(child[v][i], num ^ 1);
		barg = 0;
		if(win[child[v][i]]) 
			lose = 1;
	}
	
	if(barg){
		if(p[v][num]) 
			win[v] = 1;
	}
	
	else if(!lose) 
		win[v] = 1;
}
 
int main(){_
	cin >> n;
	for(int i = 0 ; i < n ; i ++){
		string s;
		cin >> s;
		insert(0, s);
	}
	
	cin >> m;
	for(int i = 0 ; i < m ; i ++){
		string s;
		cin >> s;
		insert(1, s);
	}
	
	dfs();
	bool ans = 0;
	for(int i = 0 ; i < 26 ; i ++)
		if(child[1][i])
			ans |= win[child[1][i]];
	
	cout << (ans ? "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