Submission #975741

#	Time	Username	Problem	Language	Result	Execution time	Memory
975741		megaminion	Vlak (COCI20_vlak)	C++17	70 / 70	18 ms	12120 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
using ll = long long;
using ld = long double;
void prt(bool f){cout<<((f)? "Yes\n" : "No\n");}
void out(){cout<<"-1\n";}
const ld PI = 2*acos(0.0);
const ld EPS = 1e-11;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const int INF = 1e9;
const int N = 5e6;
const int M = 1e6;
const int B = 26;
// #define int ll

int nxt[N][B];
bool col[N][2];
int id;
bool dp[N][2];

void add(string s, bool f)
{
	int cur = 0;
	for(auto &c : s)
	{
		int x = c - 'a';
		if(nxt[cur][x] == 0)
		{
			nxt[cur][x] = ++id;
		}
		cur = nxt[cur][x];
		col[cur][f] = true;
	}
}

void dfs(int u = 0)
{
	for(int i = 0; i < B; ++i)
	{
		if(nxt[u][i])
		{
			dfs(nxt[u][i]);
		}
	}
	bool ans[2] = {false, false};
	for(int i = 0; i < B; ++i)
	{
		if(nxt[u][i] && col[nxt[u][i]][0])
		{
			ans[0] |= !dp[nxt[u][i]][1];
		}
	}
	for(int i = 0; i < B; ++i)
	{
		if(nxt[u][i] && col[nxt[u][i]][1])
		{
			ans[1] |= !dp[nxt[u][i]][0];
		}
	}
	dp[u][0] = ans[0];
	dp[u][1] = ans[1];
}

void ah_shit_here_we_go_again()
{
	string s;
	int n, m; cin>>n;
	for(int i = 0; i < n; ++i)
		cin>>s, add(s, false);
	cin>>m;
	for(int i = 0; i < m; ++i)
		cin>>s, add(s, true);
	col[0][0] = col[0][1] = true;
	dfs();
	if(dp[0][0])
		cout<<"Nina";
	else
		cout<<"Emilija";
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    for(int i = 1; i <= t; ++i)
        ah_shit_here_we_go_again();
    return 0;
}

/*

*/

• 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