oj.uz

Submission #703579

# Submission time Handle Problem Language Result Execution time Memory
703579 2023-02-27T17:44:19 Z PoonYaPat Vlak (COCI20_vlak) C++14
70 / 70
 20 ms 21880 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
    char c;
    int depth;
    bool k1,k2,win,endword;
    node *child[26];
};

struct node *getnode(char c, int depth) {
    struct node *pnode=new node;
    pnode->c=c;
    pnode->depth=depth;
    pnode->k1=false;
    pnode->k2=false;
    pnode->win=false;
    pnode->endword=false;
    for (int i=0; i<26; ++i) pnode->child[i]=NULL;
    return pnode;
};

//Nina
void add1(string s, node *pnode) {
    for (int i=0; i<s.size(); ++i) {
        int idx=s[i]-'a';
        if (!pnode->child[idx]) pnode->child[idx]=getnode(s[i],pnode->depth+1);
        pnode->endword=false;
        pnode=pnode->child[idx];
        pnode->k1=true;
    }
    pnode->endword=true;
}

//Emilia
void add2(string s, node *pnode) {
    for (int i=0; i<s.size(); ++i) {
        int idx=s[i]-'a';
        if (!pnode->child[idx]) pnode->child[idx]=getnode(s[i],pnode->depth+1);
        pnode->endword=false;
        pnode=pnode->child[idx];
        pnode->k2=true;
    }
    pnode->endword=true;
}

bool dfs(node *pnode) {
    //game end
    if (pnode->depth%2==0 && !pnode->k2) return true;
    if (pnode->depth%2==1 && !pnode->k1) return false;

    if (pnode->endword) {
        if (pnode->depth%2==1) return true;
        else return false;
    }

    //game continue
    if (pnode->depth%2==0) {
        bool win=false;
        for (int i=0; i<26; ++i) {
            if (pnode->child[i]) win|=dfs(pnode->child[i]);
        }
        return win;
    } else {
        bool win=true;
        for (int i=0; i<26; ++i) {
            if (pnode->child[i]) win&=dfs(pnode->child[i]);
        }
        return win;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; string s;
    struct node *trie = getnode('*',0);
    trie->k2=true;

    cin>>n;
    while (n--) cin>>s, add1(s,trie);
    cin>>n;
    while (n--) cin>>s, add2(s,trie);

    if (dfs(trie)) cout<<"Nina";
    else cout<<"Emilija";

}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 572 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 468 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 440 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 468 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 17 ms 20480 KB Output is correct
2 Correct 20 ms 19136 KB Output is correct
3 Correct 15 ms 18112 KB Output is correct
4 Correct 17 ms 19924 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20864 KB Output is correct
2 Correct 17 ms 21880 KB Output is correct
3 Correct 12 ms 20116 KB Output is correct
4 Correct 14 ms 20424 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19724 KB Output is correct
2 Correct 14 ms 19284 KB Output is correct
3 Correct 15 ms 19740 KB Output is correct
4 Correct 16 ms 20980 KB Output is correct