oj.uz

Submission #947952

# Submission time Handle Problem Language Result Execution time Memory
947952 2024-03-17T09:43:43 Z Magneto_ Vlak (COCI20_vlak) C++14
70 / 70
 31 ms 26972 KB 
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<algorithm>
#define int long long int
#define vec vector<int>
#define endl '\n'
#define f(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
using namespace std;

class Node{
public:
    int end;
    int count1, count2;
    vector<Node*>arr;
    Node(){
        end = 0;
        count1 = 0;
        count2 = 0;
        arr.resize(26, NULL);
    }
};

class Trie{  
public:
    Node* root;
    //vec dp;
    map<pair<Node*, int>, int>dp;
    Trie(){
        root = NULL;
        //dp.resize(5005, -1);
    }
    void insert(string &t, int x){
        if(!root) root = new Node();
        Node* curr = root;
        int n = t.length();
        f(i, n){
            int c = t[i] - 'a';
            if(curr->arr[c] == NULL){
                curr->arr[c] = new Node();
            }
            if(x == 0) curr->arr[c]->count1++;
            else curr->arr[c]->count2++;

            if(i == n-1){
                curr->arr[c]->end=1;
            }
            curr = curr->arr[c];
        }
    }
    // int getPrefixCount(string &t){
    //     Node* curr = root;
    //     int n = t.length(); int ans = 0;
    //     f(i, n){
    //         int c = t[i] - 'a';
    //         if(curr->arr[c] == NULL){
    //             break;
    //         }
    //         if(i == n-1){
    //             ans = curr->arr[c]->count;
    //         }
    //         curr = curr->arr[c];
    //     }
    //     return ans;
    // }
    // int totalWays(string &t, int i){
    //     int n = t.length();
    //     if(i == n) return 1;
    //     if(dp[i] != -1) return dp[i];
    //     int ans = 0;
    //     Node* curr = root;
    //     for(int k=i;k<n;k++){
    //         int c = t[k] - 'a';
    //         if(curr->arr[c] == NULL) break;
    //         if(curr->arr[c]->end) (ans += totalWays(t,k+1))%=mod;
    //         curr = curr->arr[c];
    //     }
    //     return dp[i] = ans;
    // }
    int rec(Node* curr, int turn){
        if(curr == NULL) return 0;
        if(dp.find({curr, turn}) != dp.end()) return dp[{curr, turn}];
        int win = 0;
        f(j, 26){
            if(curr->arr[j] == NULL) continue;
            if(turn == 0){
                if(curr->arr[j]->count1){
                    win |= !rec(curr->arr[j], !turn);
                }
            }else{
                if(curr->arr[j]->count2){
                    win |= !rec(curr->arr[j], !turn);
                }
            }
        }
        return dp[{curr, turn}] = win;
    }
};


signed main(){
    int m,n; cin>>m;
    Trie *trie = new Trie();
    while(m--){
        string t; cin>>t;
        trie->insert(t, 0);
    }
    cin>>n;
    while(n--){
        string t; cin>>t;
        trie->insert(t, 1);
    }
    cout<<(trie->rec(trie->root, 0) ? "Nina" : "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 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 #3
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 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 1 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 25436 KB Output is correct
2 Correct 24 ms 23644 KB Output is correct
3 Correct 28 ms 22352 KB Output is correct
4 Correct 25 ms 24660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 25684 KB Output is correct
2 Correct 23 ms 26972 KB Output is correct
3 Correct 21 ms 24668 KB Output is correct
4 Correct 22 ms 25180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24412 KB Output is correct
2 Correct 22 ms 23644 KB Output is correct
3 Correct 23 ms 24392 KB Output is correct
4 Correct 31 ms 26000 KB Output is correct