제출 #592966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592966		nguyen31hoang08minh2003	Vlak (COCI20_vlak)	C++14	70 / 70	35 ms	30388 KiB

Main

/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |
|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  |
|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |
|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|
|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |
|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  |
|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |
|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  |
|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |
|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|
|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |
|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  |
|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class Trie {
private:
    int n;
    vvi trie, cnt;
    vector<vector<bool> > seen, dp;

    bool DP(int x, int y) {
        if (!seen[x][y]) {
            int z;
            seen[x][y] = true;
            fore(t, 0, 26) {
                z = trie[x][t];
                if (z < 0 || cnt[z][y] <= 0)
                    continue;
                if (!DP(z, y ^ 1))
                    return dp[x][y] = true;
            }
        }
        return dp[x][y];
    }

public:
    Trie(): n(0), trie(1, vi(26, -1)), cnt(1, vi(2, 0)) {};
    void append(const string &s, const short flag) {
        int x = 0, y;
        for (const char &c : s) {
            y = c - 'a';
            if (trie[x][y] < 0) {
                trie[x][y] = ++n;
                trie.pb(vi(26, -1));
                cnt.pb(vi(2, 0));
            }
            x = trie[x][y];
            ++cnt[x][flag];
        }
    }

    void solve() {
        dp.resize(n + 1, vector<bool>(2, false));
        seen.resize(n + 1, vector<bool>(2, false));
        if (DP(0, false))
            cout << "Nina\n";
        else
            cout << "Emilija\n";
    }
} trie;

int n, m;

int main() {
    string word;
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> n;
    fore(_, 0, n) {
        cin >> word;
        trie.append(word, 0);
    }
    cin >> m;
    fore(_, 0, m) {
        cin >> word;
        trie.append(word, 1);
    }
    trie.solve();
    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