oj.uz

Submission #632864

# Submission time Handle Problem Language Result Execution time Memory
632864 2022-08-21T02:48:10 Z van_hoang Vlak (COCI20_vlak) C++17
70 / 70
 45 ms 102716 KB 
#include "bits/stdc++.h"

using namespace std;

#ifndef LOCAL
#define debug(...) 86
#endif

const int maxN = 1e6 + 5;
int N, M, nxt = 1, mask[maxN][26], state[maxN];
queue<int> qu;

string ans[2] = {"Emilija", "Nina"};

bool DFS(int u, int turn) {
    if (!(state[u] & (1 << turn))) return false;
    for (int j = 0; j < 26; ++j) {
        if (mask[u][j] != -1 && !DFS(mask[u][j], turn ^ 1)) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> N;
    memset(mask, -1, sizeof mask);
    state[1] = 3;
    for (int i = 0; i < N; ++i) {
        string s; cin >> s;
        int cur = 1;
        for (auto &x : s) {
            int j = x - 'a';
            if (mask[cur][j] != -1) {
                cur = mask[cur][j];
            }
            else {
                mask[cur][j] = ++nxt;
                cur = nxt;
            }
            state[cur] |= 1;
        }
    }
    cin >> M;
    for (int i = 0; i < M; ++i) {
        string s; cin >> s;
        int cur = 1;
        for (auto &x : s) {
            int j = x - 'a';
            if (mask[cur][j] != -1) {
                cur = mask[cur][j];
            }
            else {
                mask[cur][j] = ++nxt;
                cur = nxt;
            }
            state[cur] |= 2;
        }
    }
    cout << ans[DFS(1, 0)] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 102020 KB Output is correct
2 Correct 39 ms 102024 KB Output is correct
3 Correct 37 ms 102072 KB Output is correct
4 Correct 39 ms 101964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 101968 KB Output is correct
2 Correct 39 ms 101968 KB Output is correct
3 Correct 37 ms 102024 KB Output is correct
4 Correct 40 ms 101988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 101996 KB Output is correct
2 Correct 43 ms 102100 KB Output is correct
3 Correct 37 ms 101984 KB Output is correct
4 Correct 37 ms 101956 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 102016 KB Output is correct
2 Correct 36 ms 102044 KB Output is correct
3 Correct 44 ms 102064 KB Output is correct
4 Correct 38 ms 102068 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 102320 KB Output is correct
2 Correct 41 ms 102352 KB Output is correct
3 Correct 40 ms 102476 KB Output is correct
4 Correct 41 ms 102716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102412 KB Output is correct
2 Correct 40 ms 102524 KB Output is correct
3 Correct 44 ms 102544 KB Output is correct
4 Correct 40 ms 102528 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102368 KB Output is correct
2 Correct 44 ms 102484 KB Output is correct
3 Correct 43 ms 102588 KB Output is correct
4 Correct 41 ms 102640 KB Output is correct