제출 #1194722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194722		KindaGoodGames	Vlak (COCI20_vlak)	C++20	50 / 70	15 ms	12716 KiB

Main

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

struct TrieNode{
    vector<int> child;
    bool marked;
    bool p1;
    bool p2;

    TrieNode(){
        child.resize(26, -1);
        marked = false;
        p1 = false;
        p2 = false;
    }
};

vector<TrieNode> trie;
vector<vector<bool>> dp(2, {false});

void insert(string& s, int i, int ind, int k){
    if(i+1 == s.size()){
        trie[ind].marked = true; 
        return;
    }

    if( trie[ind].child[s[i]-'a'] == -1){
        trie[ind].child[s[i]-'a'] = trie.size();
        trie.push_back(TrieNode());
        dp[0].push_back(false);
        dp[1].push_back(false);
    }
    int c = trie[ind].child[s[i]-'a'];

    if(k == 0){
        trie[c].p1 = true;
    }else{
        trie[c].p2 = true;
    }
    insert(s,i+1,c,k); 
} 

void rec(int ind, int k){
    if(trie[ind].p1 && !trie[ind].p2){
        dp[0][ind] = 1;
        return;
    }
    if(trie[ind].p1 == false && trie[ind].p2 == true){
        dp[1][ind] = 1;
        return;
    } 
    bool ch = false;
    for(int i = 0; i < 26; i++){
        int c = trie[ind].child[i];
        if(c != -1){
            ch = true;
            rec(c, 1-k);
            if(!dp[1-k][c]){
                dp[k][ind] = true;
            }
        }
    }
    if(!ch){
        dp[k][ind] = 1;
    }
}


int main(){
    trie.push_back(TrieNode());
    int n1;
    cin >> n1;

    for(int i = 0; i < n1; i++){
        string s;
        cin >> s;
        insert(s, 0, 0, 0);
    }
    
    int n2;
    cin >> n2;

    if(n1 == 0){
        cout <<"Emilija" << endl;
        return 0;
    }
    if(n2 == 0){
        cout <<"Nina" << endl;
        return 0;
    }

    for(int i = 0; i < n2; i++){
        string s;
        cin >> s;
        insert(s, 0, 0, 1);
    }
    
    rec(0,0);

    if(dp[0][0]){
        cout <<"Nina" << endl;
    }else{
        cout <<"Emilija" << endl;
    }
}

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