oj.uz

Submission #988801

# Submission time Handle Problem Language Result Execution time Memory
988801 2024-05-26T08:57:39 Z HasanV11010238 Vlak (COCI20_vlak) C++17
70 / 70
 38 ms 24656 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<<"Nina";
    }
    else{
        cout<<"Emilija";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 636 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 700 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22100 KB Output is correct
2 Correct 36 ms 20904 KB Output is correct
3 Correct 22 ms 19792 KB Output is correct
4 Correct 24 ms 21660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23380 KB Output is correct
2 Correct 24 ms 24656 KB Output is correct
3 Correct 22 ms 22792 KB Output is correct
4 Correct 37 ms 23216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21852 KB Output is correct
2 Correct 22 ms 21456 KB Output is correct
3 Correct 26 ms 21932 KB Output is correct
4 Correct 36 ms 23336 KB Output is correct