oj.uz

Submission #377395

# Submission time Handle Problem Language Result Execution time Memory
377395 2021-03-14T06:54:05 Z Vimmer Vlak (COCI20_vlak) C++14
70 / 70
 120 ms 22892 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define N 200500
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

int nx[N][26], n, m, id = 1;

int f[N], glob, j;

bool mk[N][2];

string s[N], t[N];

void rec(int v)
{
    mk[v][0] = 1;

    if (j == sz(s[glob]))
        return;

    int c = s[glob][j] - 'a';

    if (nx[v][c] == 0)
    {
        nx[v][c] = id++;
    }

    j++;

    rec(nx[v][c]);
}

void dfs(int v)
{
    mk[v][1] = 1;

    if (j == sz(t[glob]))
        return;

    int c = t[glob][j] - 'a';

    if (nx[v][c] == 0)
    {
        nx[v][c] = id++;
    }

    j++;

    dfs(nx[v][c]);
}

void dfser(int v, int p)
{
    f[v] = 0;

    for (int i = 0; i < 26; i++)
    {
        int t = nx[v][i];

        if (t == 0) continue;

        if (!mk[t][p]) continue;

        dfser(t, (p + 1) % 2);

        if (!f[t])
            f[v] = 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> s[i];

    cin >> m;

    for (int i = 0; i < m; i++)
        cin >> t[i];

    for (int i = 0; i < n; i++)
    {
        glob = i;

        j = 0;

        rec(0);
    }

    for (int i = 0; i < m; i++)
    {
        glob = i;

        j = 0;

        dfs(0);
    }

    dfser(0, 0);

    if (f[0])
    {
        pri("Nina");
    }
    else
    {
        pri("Emilija");
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13064 KB Output is correct
2 Correct 10 ms 13036 KB Output is correct
3 Correct 10 ms 13036 KB Output is correct
4 Correct 11 ms 13036 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13036 KB Output is correct
2 Correct 10 ms 13036 KB Output is correct
3 Correct 9 ms 13036 KB Output is correct
4 Correct 11 ms 13036 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22380 KB Output is correct
2 Correct 21 ms 21996 KB Output is correct
3 Correct 21 ms 21612 KB Output is correct
4 Correct 21 ms 22380 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22508 KB Output is correct
2 Correct 22 ms 22892 KB Output is correct
3 Correct 22 ms 22124 KB Output is correct
4 Correct 22 ms 22264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22124 KB Output is correct
2 Correct 24 ms 21996 KB Output is correct
3 Correct 21 ms 22024 KB Output is correct
4 Correct 120 ms 22892 KB Output is correct