제출 #1121200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121200		cpismylifeOwO	Vlak (COCI20_vlak)	C++17	70 / 70	11 ms	37068 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 2e5 + 5;

int n, m;
string a[MaxN];
string b[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> a[x];
    }
    cin >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> b[x];
    }
}

struct Node
{
    int child[26];
    int cnt[2];

    Node()
    {
        for (int x = 0; x < 26; x++)
        {
            child[x] = -1;
        }
        cnt[0] = cnt[1] = 0;
    }
};

int curPos;
Node Trie[MaxN];

void Add(int id, const string& s)
{
    int pos = 0;
    Trie[pos].cnt[id]++;
    for (char x : s)
    {
        int c = x - 'a';
        if (Trie[pos].child[c] == -1)
        {
            curPos++;
            Trie[curPos] = Node();
            Trie[pos].child[c] = curPos;
        }
        pos = Trie[pos].child[c];
        Trie[pos].cnt[id]++;
    }
}

int F[2][MaxN];

int DFS(int u, bool turn)
{
    if (F[turn][u] != -1)
    {
        return F[turn][u];
    }
    if (Trie[u].cnt[turn] == 0)
    {
        F[turn][u] = 0;
        return F[turn][u];
    }
    F[turn][u] = 1;
    for (int x = 0; x < 26; x++)
    {
        if (Trie[u].child[x] != -1)
        {
            F[turn][u] &= DFS(Trie[u].child[x], !turn);
        }
    }
    F[turn][u] = !F[turn][u];
    return F[turn][u];
}

void Exc()
{
    curPos = 0;
    Trie[curPos] = Node();
    for (int x = 1; x <= n; x++)
    {
        Add(0, a[x]);
    }
    for (int x = 1; x <= n; x++)
    {
        Add(1, b[x]);
    }
    memset(F, -1, sizeof(F));
    if (DFS(0, 0))
    {
        cout << "Nina";
    }
    else
    {
        cout << "Emilija";
    }
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• 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