oj.uz

Submission #673781

# Submission time Handle Problem Language Result Execution time Memory
673781 2022-12-22T02:57:18 Z chanhchuong123 Vlak (COCI20_vlak) C++14
70 / 70
 18 ms 22608 KB 
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}

struct Trie {
    Trie* nxt[26];
    int cnt;
    Trie() {
        for (int i = 0; i < 26; ++i)
            nxt[i] = nullptr;
        cnt = 0;
    }
} *N, *E;

void add(Trie *p, string s) {
    for (int i = 0; i < s.size(); ++i) {
        int LOVE = s[i] - 'a';
        if (p->nxt[LOVE] == nullptr) p->nxt[LOVE] = new Trie();
        p = p->nxt[LOVE]; ++p->cnt;
    }
}

const int MAX = 2e5 + 3;
int n;
string s;

bool dfs(Trie *u, Trie *v, int c, int type) {
    if (type == 0) {
        if (u->nxt[c] == nullptr) return false;
        if (v->nxt[c] == nullptr) return true;
    } else {
        if (v->nxt[c] == nullptr) return false;
        if (u->nxt[c] == nullptr) return true;
    }
    bool ok = false;
    u = u->nxt[c]; v = v->nxt[c];
    for (int cc = 0; cc < 26; ++cc) {
        ok |= dfs(u, v, cc, type ^ 1);
    }
    return !ok;
}

main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

    N = new Trie();
    E = new Trie();
    cin >> n;
    while (n--) {
        cin >> s;
        add(N, s);
    }
    cin >> n;
    while (n--) {
        cin >> s;
        add(E, s);
    }
    for (int i = 0; i < 26; i++) {
        if (dfs(N, E, i, 0)) {
            cout << "Nina";
            return 0;
        }
    }
    cout << "Emilija";
}

Compilation message

Main.cpp: In function 'void add(Trie*, std::string)':
Main.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main() {
      | ^~~~

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 576 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21072 KB Output is correct
2 Correct 15 ms 19796 KB Output is correct
3 Correct 16 ms 18732 KB Output is correct
4 Correct 14 ms 20552 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21624 KB Output is correct
2 Correct 18 ms 22608 KB Output is correct
3 Correct 14 ms 20792 KB Output is correct
4 Correct 14 ms 21076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20308 KB Output is correct
2 Correct 14 ms 19796 KB Output is correct
3 Correct 17 ms 20372 KB Output is correct
4 Correct 16 ms 21716 KB Output is correct