Submission #1038785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038785		SoMotThanhXuan	Vlak (COCI20_vlak)	C++17	70 / 70	8 ms	11356 KiB

Main

//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 / 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