Submission #1091562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091562		GuessWhoHas2Cats	Vlak (COCI20_vlak)	C++17	70 / 70	15 ms	11552 KiB

Main

#include<bits/stdc++.h>
using namespace std;
// trie结构 + 博弈论
// 建完trie树之后可以根据每个节点的深度判断当前的turn
// base case 是 如果在自己的 turn, 且不能转移到属于自己的node -> lose
// (ta的做法是对每个node记录一个cnt 数组， 其下标表示属于谁， val表示是node可被ta用)
//  **
// 博弈论的状态转移直接用，若当前点没有走进lose,调用dfs,若返回0，则相当于本节点返回1
const int N = 2e5 + 10;
int trie[N][26], cnt[N][2], lvl[N];
int node_count;
// 同样的，本题也不关注output

void add(string w, int id)
{
    int node = 0;
    cnt[node][id] ++; // 缺少则连根都进不去，每次只输出Emilija
    int l = 0;
    for(char c : w)
    {
        if(trie[node][c - 'a'] == 0)
            trie[node][c - 'a'] = ++node_count;
        node = trie[node][c - 'a'];
        lvl[node] = ++ l;
        cnt[node][id] ++;
    }
}

int f[N];
int dfs(int node)
{
    if(f[node] != -1)return f[node];
    int turn = lvl[node] & 1;
    // base case 
    // 如果当前所在的node不是当前turn能走的 -> return f[node] = 0;
    // 在curr判断，不在26个可能的走向上判断
    f[node] = 0;
    if(cnt[node][turn] == 0)return 0;
    // 0, 1 2种情况，dfs到可以判断一方为0时返回
    for(int i = 0; i < 26; i ++)
    {
        if(!trie[node][i]) continue;
        // *************
        // 这里不能再用node,是2个不同的量，child = 
        int child = trie[node][i];
        if(!dfs(child))f[node] = 1;
    }
    return f[node];
}

void getdata(int id)
{
    int n;
    cin >> n;
    while(n --)
    {
        string s;
        cin >> s;
        add(s, id);
    }
}

int main()
{
    getdata(0);
    getdata(1);
    memset(f, -1, sizeof f);
    int b = dfs(0);
    cout << (b ? "Nina" : "Emilija");
    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