oj.uz

Submission #521804

# Submission time Handle Problem Language Result Execution time Memory
521804 2022-02-03T07:52:16 Z Shin Vlak (COCI20_vlak) C++14
70 / 70
 18 ms 22628 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Node {
    Node *child[26];
    Node() {
        for (int i = 0; i < 26; i ++)
            child[i] = nullptr;
    }
};

Node *root[2];

bool dfs(Node *Nina, Node *Emi, bool t) {
    for (int c = 0; c < 26; c ++) {
        if (t) {
            if (Emi->child[c] == nullptr)
                continue;
            if (Nina->child[c] == nullptr)
                return false;
            if (!dfs(Nina->child[c], Emi->child[c], t ^ 1))
                return false;
        } else {
            if (Nina->child[c] == nullptr)
                continue;
            if (Emi->child[c] == nullptr)
                return true;
            if (dfs(Nina->child[c], Emi->child[c], t ^ 1))
                return true;
        }
    }
    return t;
}

void solve(void) {
    auto add = [&](string s, bool t) {
        Node *p = root[t];
        for (int i = 0; i < (int) s.size(); i ++) {
            int c = s[i] - 'a';
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
        }
    };


    for (int i = 0; i < 2; i ++) root[i] = new Node();

    int n; cin >> n;
    for (int i = 1; i <= n; i ++) {
        string s; cin >> s;
        add(s, 0);
    }

    int m; cin >> m;
    for (int i = 1; i <= m; i ++) {
        string s; cin >> s;
        add(s, 1);
    }

    cout << (dfs(root[0], root[1], 0) ? "Nina" : "Emilija");
}

signed main(void) {
    cin.tie(0)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 564 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 440 KB Output is correct
2 Correct 1 ms 564 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 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 16 ms 21156 KB Output is correct
2 Correct 15 ms 19788 KB Output is correct
3 Correct 18 ms 18752 KB Output is correct
4 Correct 16 ms 20556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 17 ms 22628 KB Output is correct
3 Correct 13 ms 20684 KB Output is correct
4 Correct 14 ms 21068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20396 KB Output is correct
2 Correct 13 ms 19836 KB Output is correct
3 Correct 15 ms 20308 KB Output is correct
4 Correct 17 ms 21620 KB Output is correct