Submission #1094211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094211		emptypringlescan	Vlak (COCI20_vlak)	C++17	70 / 70	15 ms	22368 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int adj[200005][26],cur;
int can[200005][2],dp[200005][2];
void add(string &s, int nd, int l, int w){
	can[nd][w]=1;
	if(l==(int)s.length()) return;
	int nxt=s[l]-'a';
	if(adj[nd][nxt]==-1){
		cur++;
		adj[nd][nxt]=cur;
	}
	add(s,adj[nd][nxt],l+1,w);
}
int yey(int nd, int w){
	if(!can[nd][w]) return dp[nd][w]=0;
	bool got=false;
	for(int i=0; i<26; i++){
		if(adj[nd][i]==-1) continue;
		if(yey(adj[nd][i],w^1)) got=true;
	}
	if(got) dp[nd][w]=0;
	else dp[nd][w]=1;
	return dp[nd][w];
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(adj,-1,sizeof(adj));
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
		string s;
		cin >> s;
		add(s,0,0,0);
	}
	cin >> n;
    for(int i=0; i<n; i++){
		string s;
		cin >> s;
		add(s,0,0,1);
	}
	if(yey(0,1)) cout << "Emilija";
	else cout << "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