oj.uz

Submission #692640

# Submission time Handle Problem Language Result Execution time Memory
692640 2023-02-02T02:52:29 Z Neos Vlak (COCI20_vlak) C++14
70 / 70
 22 ms 33156 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sz(x) (int)x.size()
#define M(x) (1ll << (x))
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, b, e) for (ll i = (b); i <= (e); i++)
#define rrep(i, b, e) for (ll i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 2e5 + 7;

int n, m;
string a[N], b[N];

struct node {
    node *nxt[26];
    bool who[2];
    node() { rep(i, 0, 25) nxt[i] = nullptr; who[0] = who[1] = 0; }
};

node *rt = new node;

void ins(string s, int w) {
    node *t = rt;
    for (int i = 0; i < sz(s); i++) {
        int id = s[i] - 'a';
        if (t->nxt[id] == nullptr) t->nxt[id] = new node;
        t = t->nxt[id];
        t->who[w] = 1;
    }
}

bool dfs(node *u, int t) {
    rep(i, 0, 25) {
        if (u->nxt[i] != nullptr && u->nxt[i]->who[t]) {
            bool st = dfs(u->nxt[i], 1 - t);
            if (!st) return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> a[i], ins(a[i], 0);
    cin >> m;
    rep(i, 1, m) cin >> b[i], ins(b[i], 1);
    cout << (dfs(rt, 0) ? "Nina" : "Emilija");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 6 ms 13012 KB Output is correct
4 Correct 7 ms 12980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13012 KB Output is correct
2 Correct 7 ms 13008 KB Output is correct
3 Correct 6 ms 13012 KB Output is correct
4 Correct 7 ms 13016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13012 KB Output is correct
2 Correct 6 ms 13012 KB Output is correct
3 Correct 6 ms 12976 KB Output is correct
4 Correct 7 ms 13012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12972 KB Output is correct
2 Correct 6 ms 13012 KB Output is correct
3 Correct 7 ms 13012 KB Output is correct
4 Correct 6 ms 13008 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31968 KB Output is correct
2 Correct 20 ms 30780 KB Output is correct
3 Correct 22 ms 29876 KB Output is correct
4 Correct 22 ms 31564 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32252 KB Output is correct
2 Correct 20 ms 33156 KB Output is correct
3 Correct 19 ms 31572 KB Output is correct
4 Correct 22 ms 31808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31316 KB Output is correct
2 Correct 21 ms 30748 KB Output is correct
3 Correct 20 ms 31336 KB Output is correct
4 Correct 21 ms 32444 KB Output is correct