Submission #377369

#	Time	Username	Problem	Language	Result	Execution time	Memory
377369		kartel	Vlak (COCI20_vlak)	C++14	70 / 70	27 ms	24812 KiB

Main

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

struct trie {
    trie *next[26];
    bool hv[26][2];

    trie () {
        for (int i = 0; i < 26; i++) {
            next[i] = NULL;
            hv[i][0] = hv[i][1] = 0;
        }
    }

    void add(string &s, int i, int n, int p) {
        if (i == n) {
            return;
        }

        int c = s[i] - 'a';

        if (next[c] == NULL) {
            next[c] = new trie();
        }
        hv[c][p] = 1;

        next[c] -> add(s, i + 1, n, p);
    }

    bool calc(int p) {
//        cerr << p << el;
        for (int i = 0; i < 26; i++) {
            if (next[i] == NULL || !hv[i][p]) {
                continue;
            }

            int w = next[i] -> calc(p ^ 1);

            if (!w) {
                return 1;
            }
        }
        return 0;
    }
};

trie b;

int n, m;
string s;

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> s;

        b.add(s, 0, sz(s), 0);
    }

    cin >> m;

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

        b.add(s, 0, sz(s), 1);
    }

    bool win = b.calc(0);

    if (win) {
        cout << "Nina" << el;
    }
    else {
        cout << "Emilija" << el;
    }
}

• 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