oj.uz

Submission #1095195

# Submission time Handle Problem Language Result Execution time Memory
1095195 2024-10-01T14:20:59 Z BF001 Vlak (COCI20_vlak) C++17
70 / 70
 22 ms 14000 KB 
#include<bits/stdc++.h>
using namespace std;
 
struct ii{
    int cnt[2];
    vector<int> nx;
    ii(){
        cnt[0] = cnt[1] = 0;
        nx.resize(26, -1);
    }
}; 

vector<ii> vec;
vector<vector<int>> dp;
string s;

void add(string s, int typ){
    int root = 0;
    for (auto x : s){
        int val = x - 'a';
        if (vec[root].nx[val] == -1){
            vec[root].nx[val] = (int) vec.size();
            vec.push_back(ii());
        }
        root = vec[root].nx[val];
        vec[root].cnt[typ]++;
    }
}

int n, m;

int go(int root, int typ){
    if (dp[typ][root] != -1) return dp[typ][root];
    int rt = 0;
    for (int i = 0; i < 26; i++){
        int nw = vec[root].nx[i];
        if (nw != -1 && vec[nw].cnt[typ]) rt |= !go(nw, !typ);
    }
    dp[typ][root] = rt;
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    vec.push_back(ii());

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

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

    dp.resize(2);
    for (int i = 0; i <= 1; i++){
        dp[i].resize((int) vec.size());
        for (int j = 0; j < (int) vec.size(); j++) dp[i][j] = -1;
    }

    if (go(0, 0)) cout << "Nina";
    else cout << "Emilija";
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13256 KB Output is correct
2 Correct 14 ms 12488 KB Output is correct
3 Correct 12 ms 11880 KB Output is correct
4 Correct 16 ms 12824 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13508 KB Output is correct
2 Correct 21 ms 14000 KB Output is correct
3 Correct 13 ms 13000 KB Output is correct
4 Correct 12 ms 13256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12680 KB Output is correct
2 Correct 15 ms 12420 KB Output is correct
3 Correct 22 ms 12744 KB Output is correct
4 Correct 16 ms 13604 KB Output is correct