oj.uz

Submission #450306

# Submission time Handle Problem Language Result Execution time Memory
450306 2021-08-02T13:32:29 Z ArianKheirandish Vlak (COCI20_vlak) C++14
70 / 70
 18 ms 11480 KB 
//in the name of god//
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)			x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair
 
const int maxn = 2e5 + 10;
const int LG = 30;
const int Inf = 1e9 + 10;
int n, m, nw = 1;
int child[maxn][LG];
bool win[maxn], p[maxn][2];

void insert(int num, const string &s){
	int v = 1;
	for(char x : s){
		p[v][num] = 1;
		if(!child[v][x - 'a']) 
			v = child[v][x - 'a'] = ++ nw;
		else 
			v = child[v][x - 'a'];
	}
	p[v][num] = 1;
}
 
void dfs(int v = 1, int num = 1){
	bool lose = 0, barg = 1;
	for(int i = 0 ; i < 26 ; i ++){
		if(!child[v][i]) 
			continue;
		dfs(child[v][i], num ^ 1);
		barg = 0;
		if(win[child[v][i]]) 
			lose = 1;
	}
	
	if(barg){
		if(p[v][num]) 
			win[v] = 1;
	}
	
	else if(!lose) 
		win[v] = 1;
}
 
int main(){_
	cin >> n;
	for(int i = 0 ; i < n ; i ++){
		string s;
		cin >> s;
		insert(0, s);
	}
	
	cin >> m;
	for(int i = 0 ; i < m ; i ++){
		string s;
		cin >> s;
		insert(1, s);
	}
	
	dfs();
	bool ans = 0;
	for(int i = 0 ; i < 26 ; i ++)
		if(child[1][i])
			ans |= win[child[1][i]];
	
	cout << (ans ? "Nina" : "Emilija") << "\n";
}

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 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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 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 332 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 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10700 KB Output is correct
2 Correct 16 ms 10108 KB Output is correct
3 Correct 18 ms 9572 KB Output is correct
4 Correct 17 ms 10400 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10960 KB Output is correct
2 Correct 16 ms 11480 KB Output is correct
3 Correct 18 ms 10512 KB Output is correct
4 Correct 16 ms 10760 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10444 KB Output is correct
2 Correct 16 ms 10056 KB Output is correct
3 Correct 16 ms 10428 KB Output is correct
4 Correct 16 ms 11052 KB Output is correct