oj.uz

Submission #592966

# Submission time Handle Problem Language Result Execution time Memory
592966 2022-07-10T00:34:44 Z nguyen31hoang08minh2003 Vlak (COCI20_vlak) C++14
70 / 70
 35 ms 30388 KB 
/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |
|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  |
|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |
|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|
|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |
|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  |
|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |
|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  |
|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |
|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|   /|\   |\\\\|////|   /|\   |\/\/|\/\/|   /|\   |\/ /|\ \/|
|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |  /\|/\  | \\\|/// |  /\|/\  | \/\|/\/ |  //|\\  | \/ | \/ |
|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  | /\/|\/\ |  \\|//  | /\ | /\ |  \/|\/  | ///|\\\ |  \/|\/  |
|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |/\/\|/\/\|   \|/   |/\ \|/ /\|   \|/   |////|\\\\|   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28412 KB Output is correct
2 Correct 30 ms 26660 KB Output is correct
3 Correct 27 ms 25132 KB Output is correct
4 Correct 30 ms 27688 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29152 KB Output is correct
2 Correct 32 ms 30388 KB Output is correct
3 Correct 30 ms 27952 KB Output is correct
4 Correct 29 ms 28412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27460 KB Output is correct
2 Correct 34 ms 26768 KB Output is correct
3 Correct 29 ms 27468 KB Output is correct
4 Correct 35 ms 29228 KB Output is correct