oj.uz

Submission #634557

# Submission time Handle Problem Language Result Execution time Memory
634557 2022-08-24T14:54:56 Z erekle Vlak (COCI20_vlak) C++17
70 / 70
 26 ms 20396 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    bool word[2]{};
    Node * child[26]{};
};
Node * root = new Node();
void addWord(string s, int type) {
    Node * cur = root;
    for (char c : s) {
        if (!cur->child[c-'a']) cur->child[c-'a'] = new Node();
        cur = cur->child[c-'a'];
        cur->word[type] = true;
    }
}
bool winner(Node * cur, int turn = 0, string s = "") {
    for (int i = 0; i < 26; ++i) {
        string t = s;
        t.push_back('a'+i);
        if (cur->child[i] && cur->child[i]->word[turn] && winner(cur->child[i], 1-turn, t) == turn) return turn;
    }
    return 1 - turn;
}

int main() {
    int n; cin >> n;
    while (n--) {
        string s; cin >> s;
        addWord(s, 0);
    }
    int m; cin >> m;
    while (m--) {
        string s; cin >> s;
        addWord(s, 1);
    }
    cout << (winner(root) ? "Emilija" : "Nina") << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19020 KB Output is correct
2 Correct 17 ms 17856 KB Output is correct
3 Correct 16 ms 16844 KB Output is correct
4 Correct 26 ms 18764 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19524 KB Output is correct
2 Correct 24 ms 20396 KB Output is correct
3 Correct 17 ms 18724 KB Output is correct
4 Correct 17 ms 19020 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18400 KB Output is correct
2 Correct 18 ms 18004 KB Output is correct
3 Correct 17 ms 18380 KB Output is correct
4 Correct 18 ms 19552 KB Output is correct