oj.uz

Submission #1094211

# Submission time Handle Problem Language Result Execution time Memory
1094211 2024-09-29T02:51:57 Z emptypringlescan Vlak (COCI20_vlak) C++17
70 / 70
 15 ms 22368 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20828 KB Output is correct
2 Correct 9 ms 20652 KB Output is correct
3 Correct 9 ms 20824 KB Output is correct
4 Correct 9 ms 20808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20824 KB Output is correct
2 Correct 9 ms 20776 KB Output is correct
3 Correct 9 ms 20780 KB Output is correct
4 Correct 9 ms 20824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20828 KB Output is correct
2 Correct 8 ms 20840 KB Output is correct
3 Correct 9 ms 20824 KB Output is correct
4 Correct 9 ms 20828 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20828 KB Output is correct
2 Correct 9 ms 20600 KB Output is correct
3 Correct 10 ms 20824 KB Output is correct
4 Correct 8 ms 20824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22364 KB Output is correct
2 Correct 14 ms 22032 KB Output is correct
3 Correct 14 ms 22108 KB Output is correct
4 Correct 13 ms 22108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22364 KB Output is correct
2 Correct 12 ms 22368 KB Output is correct
3 Correct 11 ms 22088 KB Output is correct
4 Correct 12 ms 22108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22108 KB Output is correct
2 Correct 11 ms 22108 KB Output is correct
3 Correct 14 ms 22108 KB Output is correct
4 Correct 13 ms 22364 KB Output is correct