oj.uz

Submission #938498

# Submission time Handle Problem Language Result Execution time Memory
938498 2024-03-05T08:12:45 Z asdasdqwer Vlak (COCI20_vlak) C++14
70 / 70
 28 ms 20212 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node {
    char let;

    map<char, int> ni;
    map<char, int> em;

    bool emTurn=false, niTurn=false;
    bool vis = false;
};

vector<Node> trie;

void ins(string &s, bool isEm = false) {
    int idx=0;
    for (auto &x:s) {
        if (isEm) {
            if (trie[idx].em.find(x) == trie[idx].em.end()) {
                if (trie[idx].ni.find(x) == trie[idx].ni.end()) {
                    Node n1;
                    n1.let = x;
                    trie.push_back(n1);
                    trie[idx].em[x] = (int)trie.size() - 1;
                }

                else {
                    trie[idx].em[x] = trie[idx].ni[x];
                }
            }

            idx = trie[idx].em[x];
        }

        else {
            if (trie[idx].ni.find(x) == trie[idx].ni.end()) {
                if (trie[idx].em.find(x) == trie[idx].em.end()) {
                    Node n1;
                    n1.let = x;
                    trie.push_back(n1);
                    trie[idx].ni[x] = (int)trie.size() - 1;
                }

                else {
                    trie[idx].ni[x] = trie[idx].em[x];
                }
            }
            idx = trie[idx].ni[x];
        }
    }
}

void dfs(int idx) {
    if (trie[idx].vis) return;
    trie[idx].vis = true;

    for (auto [c, i]:trie[idx].ni) {
        dfs(i);
        if (!trie[i].emTurn) {
            trie[idx].niTurn = true;
        }
    }

    for (auto [c, i]:trie[idx].em) {
        dfs(i);
        if (!trie[i].niTurn) {
            trie[idx].emTurn = true;
        }
    }
}

signed main() {
    int n;cin>>n;
    Node n1;
    trie.push_back(n1);
    for (int i=0;i<n;i++) {
        string s;cin>>s;
        ins(s);
    }

    int m;cin>>m;
    for (int i=0;i<m;i++) {
        string s;cin>>s;
        ins(s, true);
    }

    dfs(0);

    if (trie[0].niTurn) {
        cout<<"Nina\n";
    }

    else {
        cout<<"Emilija\n";
    }
}

Compilation message

Main.cpp: In function 'void dfs(int)':
Main.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [c, i]:trie[idx].ni) {
      |               ^
Main.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for (auto [c, i]:trie[idx].em) {
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 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 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
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 1 ms 600 KB Output is correct

Subtask #4
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 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18936 KB Output is correct
2 Correct 23 ms 19960 KB Output is correct
3 Correct 21 ms 19960 KB Output is correct
4 Correct 24 ms 19684 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18676 KB Output is correct
2 Correct 21 ms 18352 KB Output is correct
3 Correct 19 ms 18676 KB Output is correct
4 Correct 20 ms 19188 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 18108 KB Output is correct
2 Correct 20 ms 20212 KB Output is correct
3 Correct 21 ms 19188 KB Output is correct
4 Correct 21 ms 19192 KB Output is correct