Submission #1267067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267067		dangheo	Vlak (COCI20_vlak)	C++20	70 / 70	13 ms	22340 KiB

Main

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmb = 1e5 + 69, dicSize = 26;
const ld pi = atan(1) * 4;

/*
Xay Trie cho 2 nguoi;

Ban dau, ca 2 curleft, curright deu o root.
Tai buoc 1:
 Nina muon thang
 -> tu curleft, phai nhay xuong cac con, curright cung nhay xuong giong voi chu cai curleft nhay xuong.
 -> Nina muon biet xem co con nao lm cho Nina thang khong
Tai buoc 2:
 Den luot Emilija,
 -> Emilija muon thang
 -> Lam tuong tu nhu tren
...

Nhu vay, curleft va curright se o node tuong ung voi xau hien tai o moi Trie.

O mot node, neu la luot le, xet curleft, chan thi xet curright.
Nguoi choi hien tai thua khi va chi khi:
 +, Node khong ton tai
 +, Node khong co con nao (Khong the nhay xuong duoc
*/

int n;
string s;

struct Trie{
    struct Node{
        Node *ch[dicSize];
        
        Node(){
            fill(ch, ch + dicSize, nullptr);
        }
    };
    
    Node *root = new Node;
    
    void insert(string &s){
        Node *cur = root;
        for(char i : s){
            int d = i - 'a';
            if(cur->ch[d] == nullptr)
                cur->ch[d] = new Node;
            cur = cur->ch[d];
        }
    }
} Nani, Elimi;

void readData(){
    cin >> n;
    while(n--){
        cin >> s;
        Nani.insert(s);
    }
    cin >> n;
    while(n--){
        cin >> s;
        Elimi.insert(s);
    }
}

Trie::Node *curl = Nani.root, *curr = Elimi.root;

bool getwin(int turn){
    Trie::Node *tp;
    if(turn & 1) tp = curl;
    else tp = curr;
    
    if(tp == nullptr) return true;
    
    Trie::Node *prvl = curl, *prvr = curr;
    for(int i = 0; i <= 'z' - 'a'; ++i){
        if(tp->ch[i] == nullptr) continue;
        
        curl = curl->ch[i];
        curr = curr->ch[i];
        bool ok = getwin(turn + 1);
        curl = prvl;
        curr = prvr;
        if(ok)
            return false;
    }
    return true;
}

void solve(){
    cout << (getwin(1) ? "Emilija" : "Nina");
}

#define filename "test"

int hyathu(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    #ifdef dangheo
    freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    #else
    //freopen(filename".INP", "r", stdin);
    //freopen(filename".OUT", "w", stdout);
    #endif
    
    readData();
    solve();
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10