Submission #1235075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235075		anarch_y	Vlak (COCI20_vlak)	C++17	70 / 70	10 ms	10568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct Trie{
    static const int wmax = 2e6;
    int trie[wmax][26];
    int A[wmax][2], dp[wmax];
    int num;
 
    void insert(string x, int b){
        int cur = 0;
        A[cur][b] = 1;
        for(auto t: x){
            int c = t - 'a';
            if(trie[cur][c] == 0){
                trie[cur][c] = ++num;
            }
            A[trie[cur][c]][b] = 1;
            cur = trie[cur][c];
        }
    }

    void dfs(int cur, int b){
        for(int c=0; c<26; c++){
            if(trie[cur][c] and A[trie[cur][c]][b]){
                dfs(trie[cur][c], 1-b);
                if(dp[trie[cur][c]] == 0) dp[cur] = 1;
            }
        }
    }
};   

Trie T;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for(int i=0; i<n; i++){
        string s; cin >> s;
        T.insert(s, 0);
    }
    int m; cin >> m;
    for(int i=0; i<m; i++){
        string s; cin >> s;
        T.insert(s, 1);
    }
    T.dfs(0, 0);
    if(T.dp[0]) cout << "Nina";
    else cout << "Emilija"; 
}

• 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