Submission #529694

#	Time	Username	Problem	Language	Result	Execution time	Memory
529694		mmonteiro	Vlak (COCI20_vlak)	C++17	70 / 70	13 ms	11468 KiB

Main

#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;

// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 300010; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Trie {
    int trie[MAX][26], next_vertex = 1;
    void add(string &s) {
        int r = 0;
        for(char &c : s) {
            if(!trie[r][c - 'a']) trie[r][c - 'a'] = next_vertex++;
            r = trie[r][c - 'a'];
        }
    }
    int go(int node, int i) {
        return trie[node][i];
    }
    void dfs(int r) {
        cout << r << '\n';
        for(int i = 0; i < 26; ++i) {
            if(go(r, i)) {
                cout << char(i + 'a') << ' ' << go(r, i) << '\n';
                dfs(go(r, i));
            }
        }
    }
} nina, emi;

int n, m;
int dp[MAX][2], seen[MAX][2];

int sol(int node_nina, int turn, int node_emi) {
    if(!node_nina and node_emi or !node_emi and node_nina)
        return 0;

    if(seen[node_nina][turn]) return dp[node_nina][turn];

    int win = 0;
    for(int i = 0; i < 26; ++i) {
        int new_nin_nod;
        int new_emi_nod;

        if(!turn) { // nina's turn
            new_nin_nod = nina.go(node_nina, i);
            if(new_nin_nod) {
                new_emi_nod = emi.go(node_emi, i);
                if(!sol(new_nin_nod, turn ^ 1, new_emi_nod))
                    win = 1;
            }
        } else { // emi's turn
            new_emi_nod = emi.go(node_emi, i);
            if(new_emi_nod) {
                new_nin_nod = nina.go(node_nina, i);
                if(!sol(new_nin_nod, turn ^ 1, new_emi_nod))
                    win = 1;
            }
        }
    }

    seen[node_nina][turn] = 1;
    return dp[node_nina][turn] = win;
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        nina.add(s);
    }
    cin >> m;
    for(int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        emi.add(s);
    }

    // nina.dfs(0);
    // cout << endl;
    // emi.dfs(0);

    int flag = sol(0, 0, 0);

    cout << (flag ? "Nina" : "Emilija") << '\n';
}

int32_t main() {

	fastio;
	int t = 1;
	//cin >> t;
	for(int caso = 1; caso <= t; ++caso) {
		//cout << "Case #" << caso << ": ";
		solve();
	}

	return 0;
}

/*
Before submit:
	Check the corners cases
	Check solution restrictions

For implementation solutions:
	Check the flow of the variables

For intervals problems:
	Think about two pointers

For complete search:
	Think about cuts

If you get WA:
	Reread your code looking for stupid typos
	Try various manual testcases 
	Recheck the correctness of your algorithm
	Reread the statement
	Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
	Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
	Change the coder (if you're with a team)
	Give up. You may have other tasks to solve.
*/

Compilation message (stderr)

Main.cpp: In function 'int sol(int, int, int)':
Main.cpp:58:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     if(!node_nina and node_emi or !node_emi and node_nina)
      |        ~~~~~~~~~~~^~~~~~~~~~~~

• 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