oj.uz

Submission #377369

# Submission time Handle Problem Language Result Execution time Memory
377369 2021-03-14T06:18:45 Z kartel Vlak (COCI20_vlak) C++14
70 / 70
 27 ms 24812 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23148 KB Output is correct
2 Correct 25 ms 21740 KB Output is correct
3 Correct 21 ms 20460 KB Output is correct
4 Correct 24 ms 22636 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23660 KB Output is correct
2 Correct 23 ms 24812 KB Output is correct
3 Correct 22 ms 22764 KB Output is correct
4 Correct 22 ms 23148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22380 KB Output is correct
2 Correct 24 ms 21868 KB Output is correct
3 Correct 23 ms 22380 KB Output is correct
4 Correct 27 ms 23916 KB Output is correct