oj.uz

Submission #446566

# Submission time Handle Problem Language Result Execution time Memory
446566 2021-07-22T12:44:48 Z Arinoor Vlak (COCI20_vlak) C++17
70 / 70
 22 ms 20428 KB 
#include <bits/stdc++.h>
using namespace std;

#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x)			x.begin(), x.end()
#define pb				push_back
#define mp				make_pai

typedef long long ll;
const int maxn = 2e5 + 10;
const int maxalpha = 26;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

struct Trie{
	struct node{
		node * child[maxalpha];
		bool N, E;
		int h;

		node(){
			for(int i = 0; i < maxalpha; i ++)
				child[i] = nullptr;
			N = E = false;
			h = 0;
		}

		node *getChild(int c){
			if(child[c] == nullptr){
				child[c] = new node();
				child[c]->h = h + 1;
			}
			return child[c];
		}

	};
	
	node * root;

	Trie(){
		root = new node();
	}

	void add(const string *s, char player){
		node *cur = root;
		for(char c : *s){
			cur = cur->getChild(c - 'a');
			if(player == 'N')
				cur->N = true;
			else
				cur->E = true;
		}
	}

	bool dfs(node *v){
		bool fg = false;
		for(int i = 0; i < maxalpha; i ++){
			if(v->child[i] != nullptr){
				node *u = v->child[i];
				if(v->h % 2 == 0 and u->N or v->h % 2 == 1 and u->E){
					if(!dfs(u))
						fg = true;
				}
			}
		}
		return fg;
	}

} T;

int main(){
	ios;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		string s;
		cin >> s;
		T.add(&s, 'N');
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; i ++){
		string s;
		cin >> s;
		T.add(&s, 'E');
	}
	if(T.dfs(T.root))
		cout << "Nina\n";
	else
		cout << "Emilija\n";

}

Compilation message

Main.cpp: In member function 'bool Trie::dfs(Trie::node*)':
Main.cpp:60:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |     if(v->h % 2 == 0 and u->N or v->h % 2 == 1 and u->E){
      |        ~~~~~~~~~~~~~~^~~~~~~~

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 460 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 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 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 460 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 20 ms 19148 KB Output is correct
2 Correct 20 ms 17884 KB Output is correct
3 Correct 18 ms 16972 KB Output is correct
4 Correct 20 ms 18656 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19584 KB Output is correct
2 Correct 18 ms 20428 KB Output is correct
3 Correct 21 ms 18812 KB Output is correct
4 Correct 18 ms 19080 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18500 KB Output is correct
2 Correct 17 ms 17992 KB Output is correct
3 Correct 18 ms 18504 KB Output is correct
4 Correct 19 ms 19660 KB Output is correct