oj.uz

Submission #550933

# Submission time Handle Problem Language Result Execution time Memory
550933 2022-04-19T12:10:23 Z Jomnoi Vlak (COCI20_vlak) C++17
70 / 70
 32 ms 22612 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

class Node {
public :
	Node *c[26];
	bool finish;
	Node() : finish(false) {
		for(int i = 0; i < 26; i++) {
			c[i] = NULL;
		}
	}
};

void add(Node *node, string s, int idx) {
	if(idx == s.length()) {
		node->finish = true;
		return;
	}

	int v = s[idx] - 'a';
	if(node->c[v] == NULL) {
		node->c[v] = new Node();
	}
	add(node->c[v], s, idx + 1);
}

bool solve(Node *node1, Node *node2, bool turn) {
	bool ok;
	if(turn == true) { // Nina
		if(node1 == NULL) {
			return false;
		}

		ok = false;
		for(int i = 0; i < 26; i++) {
			if(node1->c[i] != NULL) {
				ok |= solve(node1->c[i], node2->c[i], turn ^ true);
			}
		}
	}
	else { // Emilija
		if(node2 == NULL) {
			return true;
		}

		ok = true;
		for(int i = 0; i < 26; i++) {
			if(node2->c[i] != NULL) {
				ok &= solve(node1->c[i], node2->c[i], turn ^ true);
			}
		}
	}
	return ok;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	Node *root1 = new Node();
	for(int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		add(root1, s, 0);
	}

	int m;
	cin >> m;
	Node *root2 = new Node();
	for(int i = 1; i <= m; i++) {
		string s;
		cin >> s;
		add(root2, s, 0);
	}

	if(solve(root1, root2, true) == true) {
		cout << "Nina";
	}
	else {
		cout << "Emilija";
	}
	return 0;
}

Compilation message

Main.cpp: In function 'void add(Node*, std::string, int)':
Main.cpp:17:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  if(idx == s.length()) {
      |     ~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21076 KB Output is correct
2 Correct 21 ms 19824 KB Output is correct
3 Correct 22 ms 18760 KB Output is correct
4 Correct 25 ms 20548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 21520 KB Output is correct
2 Correct 24 ms 22612 KB Output is correct
3 Correct 24 ms 20788 KB Output is correct
4 Correct 23 ms 21028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20300 KB Output is correct
2 Correct 21 ms 19892 KB Output is correct
3 Correct 23 ms 20308 KB Output is correct
4 Correct 25 ms 21644 KB Output is correct