oj.uz

Submission #975741

# Submission time Handle Problem Language Result Execution time Memory
975741 2024-05-05T19:54:36 Z megaminion Vlak (COCI20_vlak) C++17
70 / 70
 18 ms 12120 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 532 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9560 KB Output is correct
2 Correct 15 ms 9052 KB Output is correct
3 Correct 13 ms 8540 KB Output is correct
4 Correct 18 ms 9308 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9820 KB Output is correct
2 Correct 16 ms 12120 KB Output is correct
3 Correct 14 ms 9304 KB Output is correct
4 Correct 13 ms 9564 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9304 KB Output is correct
2 Correct 14 ms 9052 KB Output is correct
3 Correct 14 ms 9304 KB Output is correct
4 Correct 15 ms 9820 KB Output is correct