# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
900651 |
2024-01-08T19:19:00 Z |
vanea |
Vlak (COCI20_vlak) |
C++14 |
|
15 ms |
10268 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
int trie[mxN][26], dp[mxN];
int cnt = 0;
bool stop[mxN][2];
string alpha = "abcdefghijklmnopqrstuvwxyz";
void insert(string s, int flag) {
int node = 0;
for(auto c : s) {
if(trie[node][c-'a'] == 0) trie[node][c-'a'] = ++cnt;
node = trie[node][c-'a'];
}
stop[node][flag] = true;
}
void dfs(int node, int lvl) {
if(lvl & 1) dp[node] = 1;
else dp[node] = 2;
bool leaf = true;
for(auto c : alpha) {
int k = trie[node][c-'a'];
if(k) {
dfs(k, lvl+1);
leaf = false;
if(lvl & 1) dp[node] = max(dp[node], dp[k]);
else dp[node] = min(dp[node], dp[k]);
}
}
if(leaf) {
if(stop[node][0] && stop[node][1]) {
if(lvl & 1) dp[node] = 1;
else dp[node] = 2;
}
else if(stop[node][0]) dp[node] = 1;
else dp[node] = 2;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
insert(s, 0);
}
int m;
cin >> m;
for(int i = 0; i < m; i++) {
string s;
cin >> s;
insert(s, 1);
}
dfs(0, 0);
cout << (dp[0] == 1 ? "Nina" : "Emilija");
return 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 |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9564 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8540 KB |
Output is correct |
4 |
Correct |
11 ms |
9304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9820 KB |
Output is correct |
2 |
Correct |
14 ms |
10268 KB |
Output is correct |
3 |
Correct |
10 ms |
9308 KB |
Output is correct |
4 |
Correct |
10 ms |
9564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
9308 KB |
Output is correct |
2 |
Correct |
10 ms |
9052 KB |
Output is correct |
3 |
Correct |
13 ms |
9308 KB |
Output is correct |
4 |
Correct |
10 ms |
9820 KB |
Output is correct |