Submission #521804

#	Time	Username	Problem	Language	Result	Execution time	Memory
521804		Shin	Vlak (COCI20_vlak)	C++14	70 / 70	18 ms	22628 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10