Submission #1259366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259366		minhpk	Vlak (COCI20_vlak)	C++20	70 / 70	31 ms	59716 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

int child[400005][27];
int cur;
int path[400005][27][2];
int dp[400005][2];
void add(string s,int t){
    int k=0;
    for (auto c:s){
         if (child[k][c-'a']==0){
             cur++;
             child[k][c-'a']=cur;
         }
         path[k][c-'a'][t]=1;
         k=child[k][c-'a'];
    }
}
bool vis[400005][2];
int dfs(int i,int turn){
     if (vis[i][turn]){
         return dp[i][turn];
     }
     vis[i][turn]=1;
     dp[i][turn]=1-turn;

     int take[2]={0};
     for (int j=0;j<26;j++){
          if (path[i][j][turn]){
              int k=child[i][j];
              take[dfs(k,1-turn)]++;
          }
     }
     if (turn==1 && take[1]){
         dp[i][turn]=1;
     }
     if (turn==0 && take[0]){
         dp[i][turn]=0;
     }
     return dp[i][turn];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    cin >> a;
    for (int i=1;i<=a;i++){
         string s;
         cin >> s;
         add(s,0);
    }
    int b;
    cin >> b;
    for (int i=1;i<=b;i++){
         string s;
         cin >> s;
         add(s,1);
    }
    dfs(0,0);
    if (dp[0][0]==0){
        cout << "Nina" << "\n";
    }else{
        cout << "Emilija" << "\n";
    }
    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