oj.uz

Submission #480315

# Submission time Handle Problem Language Result Execution time Memory
480315 2021-10-15T15:48:37 Z lukameladze Vlak (COCI20_vlak) C++14
70 / 70
 31 ms 12312 KB 
# 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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11448 KB Output is correct
2 Correct 25 ms 10844 KB Output is correct
3 Correct 22 ms 10212 KB Output is correct
4 Correct 31 ms 11284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11776 KB Output is correct
2 Correct 25 ms 12312 KB Output is correct
3 Correct 21 ms 11340 KB Output is correct
4 Correct 23 ms 11404 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11148 KB Output is correct
2 Correct 25 ms 10892 KB Output is correct
3 Correct 24 ms 11156 KB Output is correct
4 Correct 24 ms 11848 KB Output is correct