oj.uz

Submission #513961

# Submission time Handle Problem Language Result Execution time Memory
513961 2022-01-18T01:04:15 Z KoD Vlak (COCI20_vlak) C++17
70 / 70
 23 ms 14520 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    struct Node {
        array<int, 26> child;  
        array<bool, 2> play;
        Node() {
            child.fill(-1);
            play.fill(false);
        }
    };

    vector<Node> node;
    node.emplace_back();
    node[0].play.fill(true);

    const auto child = [&](const int u, const char c) {
        if (node[u].child[c - 'a'] == -1) {
            node[u].child[c - 'a'] = node.size();
            node.emplace_back();
        }
        return node[u].child[c - 'a'];
    };

    for (int k = 0; k < 2; ++k) {
        int n;
        std::cin >> n;
        while (n--) {
            std::string s;
            std::cin >> s;
            int u = 0;
            for (const char c : s) {
                u = child(u, c);
                node[u].play[k] = true;
            }
        }
    }

    const int n = node.size();
    vector<array<bool, 2>> wins(n);
    for (int u = n - 1; u >= 0; --u) {
        for (int k = 0; k < 2; ++k) {
            if (!node[u].play[k]) {
                wins[u][k] = false;
                continue;
            }
            for (const int v : node[u].child) {
                if (v != -1 and !wins[v][k ^ 1]) {
                    wins[u][k] = true;
                    break;
                }
            }
        }
    }
    std::cout << (wins[0][0] ? "Nina" : "Emilija") << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 588 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14476 KB Output is correct
2 Correct 17 ms 14488 KB Output is correct
3 Correct 20 ms 14452 KB Output is correct
4 Correct 20 ms 14484 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14508 KB Output is correct
2 Correct 17 ms 14520 KB Output is correct
3 Correct 19 ms 14520 KB Output is correct
4 Correct 17 ms 14512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14404 KB Output is correct
2 Correct 17 ms 14500 KB Output is correct
3 Correct 22 ms 14380 KB Output is correct
4 Correct 17 ms 14496 KB Output is correct