oj.uz

Submission #1091562

# Submission time Handle Problem Language Result Execution time Memory
1091562 2024-09-21T09:28:12 Z GuessWhoHas2Cats Vlak (COCI20_vlak) C++17
70 / 70
 15 ms 11552 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10844 KB Output is correct
2 Correct 10 ms 10332 KB Output is correct
3 Correct 11 ms 9936 KB Output is correct
4 Correct 11 ms 10840 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11100 KB Output is correct
2 Correct 15 ms 11552 KB Output is correct
3 Correct 9 ms 10844 KB Output is correct
4 Correct 10 ms 10868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10584 KB Output is correct
2 Correct 13 ms 10328 KB Output is correct
3 Correct 10 ms 10612 KB Output is correct
4 Correct 10 ms 11356 KB Output is correct