Submission #480315

#	Time	Username	Problem	Language	Result	Execution time	Memory
480315		lukameladze	Vlak (COCI20_vlak)	C++14	70 / 70	31 ms	12312 KiB

Main

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int trie[10*N][30],out[10*N],red[10*N],bl[10*N],dp[10*N],cnt,n,m;
string s;
void insert(string s, int ty) {
     int cur = 1;
     for (int i = 0; i < (int)s.size(); i++) {
          char ch = s[i];
          out[cur]++;
          if (trie[cur][ch - 'a'] == 0) {
               cnt++;
               trie[cur][ch - 'a'] = cnt;
          }
          cur = trie[cur][ch - 'a'];
     }
     if (ty == 1)
     red[cur] = 1;
     else bl[cur] = 1;
}
void getans(int cur, int lvl) {
     //cout<<cur<<" "<<lvl<<endl;
     for (int i = 0; i < 26; i++) {
          if (trie[cur][i]) {
               getans(trie[cur][i],lvl + 1);
          }
     }
     if (lvl % 2 == 1) {
          if (out[cur] == 0) {
               if (bl[cur] == 1) dp[cur] = 2;
               else dp[cur] = 1;
               return ;
          }
          for (int j = 0; j < 26; j++) {
               if (trie[cur][j]) {
                    if (dp[trie[cur][j]] == 1) dp[cur] = 1;
               }
          }
          if (!dp[cur]) dp[cur] = 2;
     }
     if (lvl % 2 == 0) {
          if (out[cur] == 0) {
               if (red[cur] == 1) dp[cur] = 1;
               else dp[cur] = 2;
               return ;
          }
          for (int j = 0; j < 26; j++) {
               if (trie[cur][j]) {
                    if (dp[trie[cur][j]] == 2) dp[cur] = 2;
               }
               if (!dp[cur]) dp[cur] = 1;
          }
     }
}
main() {
     cin>>n;
     cnt = 1;
     for (int i = 1; i <= n; i++) {
          cin>>s;
          insert(s,1);
     }
     cin>>m;
     for (int i = 1; i <= m; i++) {
          cin>>s;
          insert(s,2);
     }
     getans(1,1);
     if (dp[1] == 1)
     cout<<"Nina\n"; else cout<<"Emilija\n";
}

Compilation message (stderr)

Main.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~

• 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