oj.uz

Submission #825787

# Submission time Handle Problem Language Result Execution time Memory
825787 2023-08-15T08:04:21 Z taitruong270 Vlak (COCI20_vlak) C++17
70 / 70
 89 ms 114288 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX 1000001

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)

int n, m;

struct Node{
	int lvl = 0, cnt[2] = {};
	int child[26] = {};
	Node(){
		lvl = cnt[0] = cnt[1] = 0;
		FOR(int, i, 0, 25) child[i] = -1;
	}
};

Node trie[MAX]; int len = 0;
const int root = 0;
void add(string s, int type){
	int node = root;
	trie[node].cnt[type]++;

	int lvl = 0;
	for (char c: s){
		int pos = c - 'a';
		if (trie[node].child[pos] == -1)
			trie[node].child[pos] = ++len;
		node = trie[node].child[pos];
		trie[node].lvl = ++lvl;
		trie[node].cnt[type]++;
	}
}

int f[MAX];

int dp(int node){
	Node curr = trie[node];
	int turn = curr.lvl & 1;
	
	f[node] = 0;
	if (!curr.cnt[turn]) return 0;

	FOR(int, choice, 0, 25){
		int childPos = curr.child[choice];
		if (childPos == -1) continue;
		Node child = trie[childPos];
		
		if (dp(childPos) == 0) f[node] = 1;
	}
	return f[node];
}

main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; FOR(int, i, 1, n) {string s; cin >> s; add(s, 0);}
	cin >> m; FOR(int, i, 1, m) {string s; cin >> s; add(s, 1);}

	FOR(int, i, 0, len) f[i] = -1;
	cout << (dp(root) ? "Nina" : "Emilija");
}

Compilation message

Main.cpp: In function 'int dp(int)':
Main.cpp:48:8: warning: variable 'child' set but not used [-Wunused-but-set-variable]
   48 |   Node child = trie[childPos];
      |        ^~~~~
Main.cpp: At global scope:
Main.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 113740 KB Output is correct
2 Correct 49 ms 113768 KB Output is correct
3 Correct 50 ms 113708 KB Output is correct
4 Correct 48 ms 113784 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 113712 KB Output is correct
2 Correct 51 ms 113744 KB Output is correct
3 Correct 51 ms 113824 KB Output is correct
4 Correct 51 ms 113712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 113720 KB Output is correct
2 Correct 50 ms 113740 KB Output is correct
3 Correct 52 ms 113760 KB Output is correct
4 Correct 53 ms 113816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 113820 KB Output is correct
2 Correct 51 ms 113828 KB Output is correct
3 Correct 58 ms 113712 KB Output is correct
4 Correct 53 ms 113784 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 114036 KB Output is correct
2 Correct 55 ms 114124 KB Output is correct
3 Correct 55 ms 114196 KB Output is correct
4 Correct 55 ms 114232 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 114188 KB Output is correct
2 Correct 55 ms 114128 KB Output is correct
3 Correct 55 ms 114032 KB Output is correct
4 Correct 55 ms 114056 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 114088 KB Output is correct
2 Correct 56 ms 114072 KB Output is correct
3 Correct 57 ms 114272 KB Output is correct
4 Correct 89 ms 114288 KB Output is correct