oj.uz

Submission #988800

# Submission time Handle Problem Language Result Execution time Memory
988800 2024-05-26T08:30:43 Z HasanV11010238 Vlak (COCI20_vlak) C++17
0 / 70
 45 ms 23632 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define mod 998244353
#define ll long long
int numbr = 0;
class Node{
public:
    unordered_map<char, Node*> childs;
    vector<int> col;
    int num = 0;
    Node(int nu){
        num = nu;
        col.assign(2, 0);
    }
};
Node* create(){
    Node* node = new Node(numbr);
    numbr++;
    return node;
}
void add(Node* root, string s, int co){
    Node* curr = root;
    for (auto v : s){
        if (curr->childs.find(v) == curr->childs.end()){
            curr->childs[v] = create();
        }
        curr = curr->childs[v];
        curr->col[co] = 1;
    }
}
vector<int> dp(numbr + 1, 2);
void dfs(Node* curr, int turn){
    dp[curr->num] = 1 - turn;
    int am = 0, an = 0;
    for (auto el : curr->childs){
        if (el.second->col[turn] == 1){
            am++;
            dfs(el.second, 1 - turn);
        }
        else{
            an++;
        }
        if ((dp[el.second->num] == turn) && el.second->col[turn] == 1){
            dp[curr->num] = turn;
        }
    }
    /*if (am == 0 && an == 0){
        dp[curr->num] = turn;
    }*/
}
int main(){
    int n, m;
    string s;
    Node* root = create();
    cin>>n;
    for (int i = 0; i < n; i++){
        cin>>s;
        add(root, s, 0);
    }
    cin>>m;
    for (int i = 0; i < m; i++){
        cin>>s;
        add(root, s, 1);
    }
    dp.assign(numbr + 1, 2);
    dfs(root, 0);
    if (dp[0] == 0){
        cout<<"Alice";
    }
    else{
        cout<<"Bob";
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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