oj.uz

Submission #530785

# Submission time Handle Problem Language Result Execution time Memory
530785 2022-02-26T19:37:47 Z Pietra Vlak (COCI20_vlak) C++14
70 / 70
 21 ms 18308 KB 
#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 2e5 + 5 ; 

int n, ct = 1, trie[2][maxn][32], lvl[maxn], fim[maxn], dp[maxn], ctt[2][maxn] ; 

void add(int type, string s){

	int rt = 0, nivel = 0 ; 

	for(int i = 0 ; i < (int)s.size() ; i++){
		if(type == 1 && trie[0][rt][s[i]-'a']) trie[1][rt][s[i]-'a'] = trie[0][rt][s[i]-'a'] ;  
		else if(trie[type][rt][s[i]-'a'] == 0) trie[type][rt][s[i]-'a'] = ct++ ;
		// cout << trie[type][rt][s[i]-'a'] << " " << rt << " " << s[i] - 'a' << "\n" ; 
		ctt[type][rt]++ ;
		rt = trie[type][rt][s[i]-'a'] ; 
	}

	fim[rt] = 1 ; 

}

void view(int type, int node){

	if(ctt[type][node] == 0) return ; 

	for(int i = 0 ; i < 26 ; i++){
		if(trie[type][node][i] == 0) continue ; 
		cout << trie[type][node][i] << " " << i << "\n" ; 
	}

	for(int i = 0 ; i < 26 ; i++){
		if(trie[type][node][i] == 0) continue ; 
		view(type, trie[type][node][i]) ;
	}

}

int dp_solve(int node, int turn){

	if(dp[node] != -1) return dp[node] ; 

	if(ctt[turn][node] == 0) return dp[node] = 0 ; 

	dp[node] = 0 ; 

	for(int i = 0 ; i < 26 ; i++){
		if(trie[turn][node][i] == 0) continue ; 
		if(dp_solve(trie[turn][node][i], !turn) == 0) dp[node] = 1 ; 
	}

	return dp[node] ; 

}

int32_t main(){

	string s ; 
	cin >> n ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> s ; 
		add(0, s) ; 
	}  

	// view(0, 0) ; 

	cin >> n ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> s ; 
		add(1, s) ; 
	}
	
	// view(1, 0) ; 

	memset(dp, -1, sizeof dp) ; 

	cout << (dp_solve(0, 0) ? "Nina\n" : "Emilija\n") ; 

}

Compilation message

Main.cpp: In function 'void add(int, std::string)':
Main.cpp:10:14: warning: unused variable 'nivel' [-Wunused-variable]
   10 |  int rt = 0, nivel = 0 ;
      |              ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18240 KB Output is correct
2 Correct 21 ms 17340 KB Output is correct
3 Correct 19 ms 16356 KB Output is correct
4 Correct 20 ms 17856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17100 KB Output is correct
2 Correct 17 ms 18108 KB Output is correct
3 Correct 17 ms 16708 KB Output is correct
4 Correct 19 ms 16840 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17356 KB Output is correct
2 Correct 17 ms 16940 KB Output is correct
3 Correct 20 ms 17212 KB Output is correct
4 Correct 20 ms 18308 KB Output is correct