oj.uz

Submission #559384

# Submission time Handle Problem Language Result Execution time Memory
559384 2022-05-09T17:07:08 Z kappa Vlak (COCI20_vlak) C++14
70 / 70
 26 ms 23248 KB 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int maxc = 30;

struct node{
    struct node* children[maxc];
    bool isEnd;
    int color;
};

struct node *getNode(void){
    struct node *pnode = new node;
    pnode->isEnd = false;
    for (int i = 0; i < maxc; i++)
    {
        pnode->children[i] = NULL;
    }
    return pnode;
}

void insert(struct node* root, string key, int color){
    struct node *pCrawl = root;
    for (int i = 0; i < key.length(); i++)
    {
        pCrawl->color |= color;
        int ind = key[i] - 'a';
        if(!pCrawl->children[ind]){
            pCrawl->children[ind] = getNode();
        }
        pCrawl = pCrawl->children[ind];
    }

    pCrawl->isEnd = true;
}

bool search(struct node* root, ll turn){
    if (!(root->color & (1 << turn))) {
      return 0;
    }

    for (int i = 0; i < maxc; i++) {
      if (root->children[i] && !search(root->children[i], turn ^ 1)) {
        return 1;
      }
    }
    return 0;
}

int n, m;

int main(){
    struct node *root = getNode();
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string a;
        cin >> a;
        insert(root, a, 1);
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string a;
        cin >> a;
        insert(root, a, 2);
    }
    if(search(root, 0)){
        cout << "Nina";
    }else{
        cout << "Emilija";
    }
}

Compilation message

Main.cpp: In function 'void insert(node*, std::string, int)':
Main.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < key.length(); i++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
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 596 KB Output is correct
4 Correct 1 ms 560 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 468 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 560 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 556 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21764 KB Output is correct
2 Correct 20 ms 20300 KB Output is correct
3 Correct 21 ms 19192 KB Output is correct
4 Correct 21 ms 21252 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22264 KB Output is correct
2 Correct 26 ms 23248 KB Output is correct
3 Correct 21 ms 21328 KB Output is correct
4 Correct 24 ms 21680 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21068 KB Output is correct
2 Correct 20 ms 20444 KB Output is correct
3 Correct 20 ms 20960 KB Output is correct
4 Correct 23 ms 22320 KB Output is correct