oj.uz

Submission #1006605

# Submission time Handle Problem Language Result Execution time Memory
1006605 2024-06-24T05:11:19 Z vjudge1 Vlak (COCI20_vlak) C++17
0 / 70
 14 ms 29276 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 26712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26716 KB Output is correct
2 Correct 3 ms 26716 KB Output is correct
3 Correct 4 ms 26716 KB Output is correct
4 Incorrect 4 ms 26712 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26712 KB Output is correct
2 Correct 4 ms 26716 KB Output is correct
3 Incorrect 3 ms 26716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26716 KB Output is correct
2 Correct 3 ms 26716 KB Output is correct
3 Correct 3 ms 26716 KB Output is correct
4 Incorrect 4 ms 26716 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Output is correct
2 Incorrect 12 ms 29104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 29276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -