Submission #436874

#	Time	Username	Problem	Language	Result	Execution time	Memory
436874		LptN21	Vlak (COCI20_vlak)	C++14	70 / 70	37 ms	33228 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define all(a) (a).begin(), (a).end()
#define odd(x) __builtin_parity((int)x)
#define cntbit(x) __builtin_popcount(x)
typedef long long ll;
typedef pair<int, int> ii;
const int N = 2e5+7;
const int MOD = 1e9+7;
const int oo = 1e9;

int n, m, k, t;

string a[N][2];
struct Trie{
    Trie* ch[26]; int cnt[2];
    Trie() {for(int i=0;i<26;i++) ch[i]=NULL;cnt[0]=cnt[1]=0;}
} *root=new Trie();

void add(int t, int idx) {
    Trie* p=root; k=sz(a[idx][t]);
    for(int j, i=0;i<k;i++) {
        j=a[idx][t][i]-'a';
        if(p->ch[j]==NULL) p->ch[j]=new Trie();
        p->cnt[t]++, p=p->ch[j];
    }
    p->cnt[t]++;
}
bool check(Trie* p, int turn) {
	bool ans=0;
	for(int i=0;i<26;i++) {
		if(p->ch[i]==NULL) continue;
		if(!p->ch[i]->cnt[turn]) continue;
		ans|=!check(p->ch[i], turn^1);
	}
	return ans;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    fastIO;
    cin>>n;
    for(int i=1;i<=n;add(0, i++)) cin>>a[i][0];
    cin>>m;
    for(int i=1;i<=m;add(1, i++)) cin>>a[i][1];
    if(check(root, 0)) printf("Nina");
    else printf("Emilija");
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

• 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