Submission #1006605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006605		vjudge1	Vlak (COCI20_vlak)	C++17	0 / 70	14 ms	29276 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 1;

int nxt[M][26],dep[M],ind=0;
bool val[M],andd[M],nvald[M];
vector<int> nei[M],lev;

void add(string s, bool b=1)
{
	int cur=0,n=s.size();
	for (int i=0;i<n;i++)
	{
		if (nxt[cur][s[i]-'a']==-1)
			nxt[cur][s[i]-'a']=++ind,dep[ind]=dep[cur]+1,nei[cur].push_back(ind);
		if (dep[cur]%2==0 || !val[cur])
			val[cur]=b;
		cur=nxt[cur][s[i]-'a'];
	}
	if (dep[cur]%2==0 || !val[cur])
		val[cur]=b;
}

void caland(int u)
{
	bool le=nei[u].empty();
	andd[u]=1;
	for (int i:nei[u])
	{
		caland(i);
		andd[u]&=andd[i];
	}
	if (le)
		andd[u]=!val[u],lev.push_back(u);
}

void calnvald(int u)
{
	for (int i:nei[u])
		nvald[i]|=nvald[u],calnvald(i);
}

int main()
{
	for (int i=0;i<M;i++)
		for (int j=0;j<26;j++)
			nxt[i][j]=-1;
	int n,m;
	cin>>n;
	string s;
	for (int i=0;i<n;i++)
		cin>>s,add(s);
	cin>>m;
	for (int i=0;i<m;i++)
		cin>>s,add(s,0);
	caland(0);
	for (int u=0;u<M;u++)
	{
		if (dep[u]%2==0)
			continue;
		for (int i:nei[u])
			if (andd[i])
				nvald[u]=1;
	}
	calnvald(0);
	string ans="Emilija";
	for (int i:lev)
		if (!nvald[i])
			ans="Nina";
	cout<<ans<<endl;
	
	return 0;
}

• 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