oj.uz

Submission #919496

# Submission time Handle Problem Language Result Execution time Memory
919496 2024-02-01T03:02:47 Z silverfox Vlak (COCI20_vlak) C++14
0 / 70
 16 ms 22872 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define TEST "filename"
using namespace std;

const int maxn = 200000;
class Trie {
    struct Node {
        int child[26];
        int exist, cnt;
    };

    int cur = 0;
    Node nodes[maxn+1];

    public:
        Trie() {
            memset(nodes[0].child, -1, sizeof(nodes[0].child));
            nodes[0].exist = nodes[0].cnt = 0;
        }

        int newNode() {
            cur++;
            memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
            nodes[cur].exist = nodes[cur].cnt = 0;

            return cur;
        }

        void addString(string s) {
            int pos = 0;

            for (char c: s) {
                int f = c - 'a';
                if (nodes[pos].child[f] == -1) {
                    nodes[pos].child[f] = newNode();
                }

                pos = nodes[pos].child[f];
                nodes[pos].cnt++;
            }
            nodes[pos].exist++;
        }

        int maxPrefix(string s) {
            int pos = 0;
            int len = 0;

            for (char c: s) {
                int f = c - 'a';
                if (nodes[pos].child[f] == -1) { //prefix doesnt match anymore
                    return len;
                }

                pos = nodes[pos].child[f];
                len++;
            }
            return len;
        }

        bool findLonger(string s) {
            int pos = 0;

            for (char c: s) {
                int f = c - 'a';
                pos = nodes[pos].child[f];
            }

            for (int i = 0; i < 26; i++) {
                if (nodes[pos].child[i] != -1) { return true; }
            }
            return false;
        }

        bool letterAfterPrefix(string s) {
            int pos = 0;

            for (char c: s) {
                int f = c - 'a';
                if (nodes[pos].child[f] == -1) { //prefix doesnt match anymore
                    break;
                }
                pos = nodes[pos].child[f];
            }

            for (int i = 0; i < 26; i++) {
                if (nodes[pos].child[i] != -1) { return true; }
            }
            return false;
        }

        bool ninaWin(string s) {
            int maxPref = this->maxPrefix(s);
            if (maxPref == s.size()) {
                if (this->findLonger(s)) { return false; } //B longer than A
                else {return s.size() % 2 == 1;} //B same length as A
            }

            else if (maxPref < s.size()) {
                if (this->letterAfterPrefix(s)) {return s.size() % 2 == 0; } //B and A share some prefix
                else { return true; } //B shorter than A
            }
        }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    if (false) {
        freopen(TEST".in", "r", stdin);
        freopen(TEST".out", "w", stdout);
    }

    int n; cin >> n;
    string a[n]; for (int i = 0; i < n; i++) {cin >> a[i];}

    int m; cin >> m;
    Trie trie;
    for (int i = 0; i < m; i++) {
        string s; cin >> s;
        trie.addString(s);
    }

    for (int i = 0; i < n; i++) {
        if (trie.ninaWin(a[i])) {cout << "Nina"; return 0;}
    }

    cout << "Emilija";
}

Compilation message

Main.cpp: In member function 'bool Trie::ninaWin(std::string)':
Main.cpp:95:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if (maxPref == s.size()) {
      |                 ~~~~~~~~^~~~~~~~~~~
Main.cpp:100:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             else if (maxPref < s.size()) {
      |                      ~~~~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TEST".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TEST".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'bool Trie::ninaWin(std::string)':
Main.cpp:104:9: warning: control reaches end of non-void function [-Wreturn-type]
  104 |         }
      |         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 22360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22368 KB Output is correct
2 Correct 11 ms 22316 KB Output is correct
3 Correct 11 ms 22360 KB Output is correct
4 Incorrect 12 ms 22180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22360 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Incorrect 12 ms 22360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22616 KB Output is correct
2 Correct 13 ms 22360 KB Output is correct
3 Correct 12 ms 22360 KB Output is correct
4 Incorrect 13 ms 22360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22872 KB Output is correct
2 Incorrect 15 ms 22872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 22616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 22620 KB Output isn't correct
2 Halted 0 ms 0 KB -