oj.uz

Submission #1038785

# Submission time Handle Problem Language Result Execution time Memory
1038785 2024-07-30T07:37:39 Z SoMotThanhXuan Vlak (COCI20_vlak) C++17
70 / 70
 8 ms 11356 KB 
//https://oj.uz/problem/view/COCI20_vlak
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define iii pair<int,ii>
#define vii vector<ii>
#define viii vector<iii>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define FORD(i,a,b) for(int i=b;i>=a;--i)
#define REP(i,a,b) for(int i=a;i<b;++i)
#define ALL(v) v.begin(),v.end()
void minimize(int &u,int v){
    if(v<u)u=v;
}
void maximize(int &u,int v){
    if(v>u)u=v;
}
void minimizell(long long &u,long long v){
    if(v<u)u=v;
}
void maximizell(long long &u,long long v){
    if(v>u)u=v;
}
const int maxN=2e5+2;
const int mod=1e9+7;
const int inf=1e9+8;
const long long infll=1e18;
const int fftmod=998244353;
const int LOG=19;
const int base=300;
const int inverse_mod=mod-2;
int child[26][200001];
bool belong[3][200001];
int cnt,N,M;
int f[maxN];
void insert(string &S,int type){
    int u=0;

    for(char c:S){
        int x=c-'a';
        if(child[x][u]==0)child[x][u]=++cnt;
        u=child[x][u];
        belong[type][u]=true;
    }
}
// f[u] = 0/1 neu nguoi choi hien tai dang o node u va 0 neu thang hoac thua
int calc(int u,int type){
    if(f[u]!=-1)return f[u];
    if(u!=0){
        if(belong[type][u]==false)return f[u]=0;
    }
    f[u]=0;
    FOR(c,0,25){
        if(belong[type][child[c][u]]){
            f[u]|=calc(child[c][u],3-type)^1;
        }
    }
    return f[u];
}
int main(){
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string S;
    cin >> N ;
    FOR(i,1,N){
        cin >> S;
        insert(S,1);
    }
    cin >> M;
    FOR(i,1,M){
        cin >> S;
        insert(S,2);
    }
    memset(f,-1,sizeof(f));
    cout << (calc(0,1)==1?"Nina":"Emilija");
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10844 KB Output is correct
2 Correct 7 ms 10300 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11100 KB Output is correct
2 Correct 6 ms 11356 KB Output is correct
3 Correct 7 ms 10588 KB Output is correct
4 Correct 6 ms 10844 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10588 KB Output is correct
2 Correct 6 ms 10436 KB Output is correct
3 Correct 8 ms 10548 KB Output is correct
4 Correct 7 ms 11100 KB Output is correct