Submission #1244462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244462		newsboy	Vlak (COCI20_vlak)	C++20	70 / 70	15 ms	19524 KiB

Main

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 P = 1E9 + 7;
constexpr i64 N = 1E6 + 10;
i64 trie[N][26], f[N];
i64 tot;

i64 newNode() {
    i64 x = ++tot;
    for (i64 i = 0; i < 26; i++) {
        trie[x][i] = 0;
    }
    f[x] = 0;
    return x;
};

void init() {
    tot = 0;
    newNode();
}

void add(string s, i64 t) {
    i64 o = 1;
    for (i64 i = 0; i < s.size(); i++) {
        i64& p = trie[o][s[i] - 'a'];
        if (!p) {
            p = newNode();
        }
        o = p;
        f[o] |= t;
    }
}

void solve() {
    init();
    i64 n;
    cin >> n;
    for (i64 i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s, 1);
    }
    i64 m;
    cin >> m;
    for (i64 i = 0; i < m; i++) {
        string s;
        cin >> s;
        add(s, 2);
    }
    auto dfs = [&](auto& self, i64 x, i64 d) -> bool {
        bool s = 0;
        for (i64 i = 0; i < 26; i++) {
            if (!trie[x][i] || !(f[trie[x][i]] & (1 << d))) {
                continue;
            }
            s |= !self(self, trie[x][i], d ^ 1);
        }
        return s;
        };
    cout << (dfs(dfs, 1, 0) ? "Nina" : "Emilija") << '\n';
} 

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

• 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