oj.uz

Submission #993900

# Submission time Handle Problem Language Result Execution time Memory
993900 2024-06-06T18:56:13 Z May27_th Vlak (COCI20_vlak) C++17
70 / 70
 22 ms 22004 KB 
#include<bits/stdc++.h>
using namespace std;

#define int64_t long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 10;
struct Trie {
    struct Node {
        Node* child[26];
        int exist, depth, cnt[2];

        Node () {
            for (int i = 0; i < 26; i ++) child[i] = NULL;
            exist = depth = cnt[0] = cnt[1] = 0;
        }
    };

    int cur;
    int have;
    Node* root;
    Trie() : have(0), cur(0) {
        root = new Node();
    };

    void Add(string S, int b) {
        Node* p = root;
        for (auto f : S) {
            int c = f - 'a';
            if (p->child[c] == NULL) {
                cur ++;
                p->child[c] = new Node();
            }
            p = p->child[c];
            p->cnt[b] ++;
        }
        p->exist ++;
        have ++;
    }
    // bool DeleteR(Node* p, string S, int pos) {
    //     if (pos != (int)S.size()) {
    //         int c = S[pos] - 'a';
    //         bool isDeleted = DeleteR(p->child[c], S, pos + 1);
    //         if (isDeleted) p->child[c] = NULL;
    //     } else {
    //         p->exist --;
    //     }

    //     if (p != root) {
    //         p->cnt --;
    //         if (p->cnt == 0) {
    //             delete(p);
    //             return true;
    //         }
    //     }
    //     return false;
    // }
    // void Delete(string S) {
    //     if (!find(S)) return;
    //     DeleteR(root, S, 0);
    // }

    // bool find(string S) {
    //     Node* p = root;
    //     for (auto f : S) {
    //         int c = f - 'a';
    //         if (p->child[c] == NULL) return false;
    //         p = p->child[c];
    //     }
    //     return true;
    // }

    int dfs(Node* p, int turn = 0) {
        int flag = (turn == 0 ? 0: 1);
        for (int c = 0; c < 26; c ++) {
            if (p->child[c] != NULL && p->child[c]->cnt[turn] > 0) {
                int ok = dfs(p->child[c], 1 - turn);
                if (turn == 0) flag = max(flag, ok);
                else flag = min(flag, ok); 
            }
        }
        return flag;
    }
    void Solve(void) {
        Node* p = root;
        // cout << p->depth << "\n";
        cout << (dfs(p) ? "Nina" : "Emilija") << "\n";
    }
};
void Solve(void) {
    Trie game;
    int N; cin >> N;
    for (int i = 1; i <= N; i ++) {
        string S; cin >> S;
        game.Add(S, 0);
    }
    int M; cin >> M;
    for (int i = 1; i <= M; i ++) {
        string S; cin >> S;
        game.Add(S, 1);
    }
    game.Solve();
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int Tests = 1; // cin >> Tests; 
    while (Tests --) {
        Solve();    
    }
}

Compilation message

Main.cpp: In constructor 'Trie::Trie()':
Main.cpp:22:9: warning: 'Trie::have' will be initialized after [-Wreorder]
   22 |     int have;
      |         ^~~~
Main.cpp:21:9: warning:   'int Trie::cur' [-Wreorder]
   21 |     int cur;
      |         ^~~
Main.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Trie() : have(0), cur(0) {
      |     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20580 KB Output is correct
2 Correct 16 ms 19300 KB Output is correct
3 Correct 14 ms 18140 KB Output is correct
4 Correct 16 ms 20060 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21080 KB Output is correct
2 Correct 15 ms 22004 KB Output is correct
3 Correct 13 ms 20176 KB Output is correct
4 Correct 13 ms 20576 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19804 KB Output is correct
2 Correct 13 ms 19292 KB Output is correct
3 Correct 17 ms 19808 KB Output is correct
4 Correct 14 ms 21084 KB Output is correct