| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 872282 |
2023-11-12T17:06:48 Z |
ObadaKh |
Vlak (COCI20_vlak) |
C++17 |
|
16 ms |
22620 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
/*-------------------------*/
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define Dracarys ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
template<typename T> using indexed_multiset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<ll, int> pi;
const int N = 2e5 + 10;
const int infi = 1e9 + 10;
const ll infl = 1e18 + 10;
const int MOD = 1e9 + 7;
const ld eps = 1e-9;
string ScanString() {
char ch[100000];
scanf("%s", ch);
return ch;
}
const int CHAR = 26;
struct TrieNode {
TrieNode *child[CHAR];
int Cnt, End;
TrieNode() {
memset(child, 0, sizeof child);
Cnt = End = 0;
}
void add(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0) child[cur] = new TrieNode();
child[cur]->Cnt++;
if (i == s.size() - 1) {
child[cur]->End++;
return;
}
child[cur]->add(i + 1, s);
}
void add(string &s) {
add(0, s);
}
void erase(int i, string &s) {
int cur = s[i] - 'a';
child[cur]->Cnt--;
if (i == s.size() - 1) {
child[cur]->End--;
return;
}
child[cur]->erase(i + 1, s);
if (!child[cur]->Cnt) {
delete child[cur];
child[cur] = 0;
}
}
void erase(string &s) {
if (!find(s))return;
erase(0, s);
}
bool find(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0)return 0;
if (i == s.size() - 1) {
return child[cur]->End > 0;
}
return child[cur]->find(i + 1, s);
}
bool find(string &s) {
return find(0, s);
}
int CntPrefix(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0)return 0;
if (i == s.size() - 1) {
return child[cur]->Cnt;
}
return child[cur]->CntPrefix(i + 1, s);
}
int CntPrefix(string &s) {
return CntPrefix(0, s);
}
void clear() {
for (int i = 0; i < CHAR; i++)
if (child[i])
child[i]->clear(), delete child[i], child[i] = 0;
}
};
int Nina = 0, Emilija = 0;
TrieNode *Root1 = new TrieNode();
TrieNode *Root2 = new TrieNode();
void Dp(TrieNode *tr1, TrieNode *tr2, bool turn) {
if (turn) {
for (int i = 0; i < 26; i++) {
if (tr1->child[i] && !tr2->child[i])
Nina++;
else if (tr1->child[i] && tr2->child[i])
Dp(tr1->child[i], tr2->child[i], !turn);
}
} else {
for (int i = 0; i < 26; i++) {
if (tr2->child[i] && !tr1->child[i])
Emilija++;
else if (tr1->child[i] && tr2->child[i])
Dp(tr1->child[i], tr2->child[i], !turn);
}
}
}
void RunTime(int Tc) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
Root1->add(s);
}
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
Root2->add(s);
}
Dp(Root1, Root2, 1);
if (Nina >= Emilija)cout << "Nina" << endl;
else cout << "Emilija" << endl;
}
int main() {
Dracarys
int T = 1;
//cin >> T;
for (int Tc = 1; Tc <= T; Tc++) {
RunTime(Tc);
}
return 0;
}
Compilation message
Main.cpp: In member function 'void TrieNode::add(int, std::string&)':
Main.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
Main.cpp: In member function 'void TrieNode::erase(int, std::string&)':
Main.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
Main.cpp: In member function 'bool TrieNode::find(int, std::string&)':
Main.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
Main.cpp: In member function 'int TrieNode::CntPrefix(int, std::string&)':
Main.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'std::string ScanString()':
Main.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%s", ch);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
21084 KB |
Output is correct |
| 2 |
Correct |
13 ms |
20056 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
18976 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21532 KB |
Output is correct |
| 2 |
Correct |
14 ms |
22620 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
21080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
20316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
