oj.uz

Submission #370027

# Submission time Handle Problem Language Result Execution time Memory
370027 2021-02-23T00:09:51 Z penguinhacker Vlak (COCI20_vlak) C++14
70 / 70
 58 ms 15752 KB 
// source: https://oj.uz/problem/view/COCI20_vlak
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int ALP=26;
struct Node {
	int nxt[ALP];
	Node() {fill(nxt, nxt+ALP, -1);}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void add(string s) {
		int cur=0;
		for (char ch: s) {
			int c=ch-'a';
			if (trie[cur].nxt[c]==-1) {
				trie[cur].nxt[c]=trie.size();
				trie.emplace_back();
			}
			cur=trie[cur].nxt[c];
		}
	}
} t1, t2;

bool solve(int p1, int p2, Trie& x, Trie& y) {
	for (int i = 0; i < 26; ++i) {
		if (x.trie[p1].nxt[i] != -1) {
			if (y.trie[p2].nxt[i] == -1) return 1;
			if (!solve(y.trie[p2].nxt[i], x.trie[p1].nxt[i], y, x)) return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	while(n--) {
		string s; cin >> s;
		t1.add(s);
	}
	cin >> n;
	while(n--) {
		string s; cin >> s;
		t2.add(s);
	}
	cout << (solve(0, 0, t1, t2) ? "Nina" : "Emilija") << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15324 KB Output is correct
2 Correct 19 ms 15064 KB Output is correct
3 Correct 19 ms 14812 KB Output is correct
4 Correct 19 ms 15196 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15452 KB Output is correct
2 Correct 21 ms 15752 KB Output is correct
3 Correct 58 ms 15324 KB Output is correct
4 Correct 21 ms 15324 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15192 KB Output is correct
2 Correct 19 ms 15096 KB Output is correct
3 Correct 18 ms 15192 KB Output is correct
4 Correct 19 ms 15448 KB Output is correct