oj.uz

Submission #436874

# Submission time Handle Problem Language Result Execution time Memory
436874 2021-06-25T07:13:36 Z LptN21 Vlak (COCI20_vlak) C++14
70 / 70
 37 ms 33228 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13012 KB Output is correct
2 Correct 10 ms 13004 KB Output is correct
3 Correct 10 ms 13092 KB Output is correct
4 Correct 10 ms 13004 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13132 KB Output is correct
2 Correct 9 ms 13004 KB Output is correct
3 Correct 9 ms 13004 KB Output is correct
4 Correct 9 ms 13004 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13004 KB Output is correct
2 Correct 8 ms 13048 KB Output is correct
3 Correct 9 ms 13004 KB Output is correct
4 Correct 11 ms 13004 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13004 KB Output is correct
2 Correct 11 ms 13004 KB Output is correct
3 Correct 9 ms 12972 KB Output is correct
4 Correct 9 ms 13004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31948 KB Output is correct
2 Correct 31 ms 30796 KB Output is correct
3 Correct 29 ms 29772 KB Output is correct
4 Correct 34 ms 31660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32304 KB Output is correct
2 Correct 31 ms 33228 KB Output is correct
3 Correct 29 ms 31564 KB Output is correct
4 Correct 29 ms 31956 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 31252 KB Output is correct
2 Correct 35 ms 30876 KB Output is correct
3 Correct 34 ms 31300 KB Output is correct
4 Correct 33 ms 32520 KB Output is correct