Submission #377395

#	Time	Username	Problem	Language	Result	Execution time	Memory
377395		Vimmer	Vlak (COCI20_vlak)	C++14	70 / 70	120 ms	22892 KiB

Main

#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 / 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