oj.uz

Submission #391800

# Submission time Handle Problem Language Result Execution time Memory
391800 2021-04-19T23:17:19 Z ahmet Vlak (COCI20_vlak) C++14
70 / 70
 17 ms 21660 KB 
#include <bits/stdc++.h>
using namespace std;
#define zaman cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))	
#define endl '\n'
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
const int mx=2e5+6;
const string ans[]={"Nina","Emilija"};
struct node{
	int edge[26];
	int last=-1;//0-Nina 1-Emilija
}trie[mx];
int no=1;

void trieAdd(string s,int res){// -1-Nothing 0-Nina 1-Emilija 2-both
	int curr=1;
	for(int i=0;i<s.size();++i){
		int ch=s[i]-'a';
		if(trie[curr].edge[ch]==0)
			trie[curr].edge[ch]=++no;
		curr=trie[curr].edge[ch];
	}
	if(trie[curr].last>-1 and trie[curr].last!=res)trie[curr].last=2;
	else trie[curr].last=res;
}
int solve(int node,int x){// x:0 Nina     x:1 Emilija  x:2 Both

	for(int i=0;i<26;++i){
		if(trie[node].edge[i]==0)continue;
		int res=solve(trie[node].edge[i],1-x);
		if(res==2)return x;
		if(res==x)return x;
	}
	if(trie[node].last==2)return 1-x;	
	if(trie[node].last>-1)return trie[node].last;
	return 1-x;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int x,y;cin >> x;
	rep(i,x){
		string s;cin >> s;
		trieAdd(s,0);
	}
	cin >> y;
	rep(i,y){
		string s;cin >> s;
		trieAdd(s,1);
	}
	cout << ans[solve(1,0)] << endl;
}

Compilation message

Main.cpp: In function 'void trieAdd(std::string, int)':
Main.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<s.size();++i){
      |              ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
      |                                ^
Main.cpp:45:2: note: in expansion of macro 'rep'
   45 |  rep(i,x){
      |  ^~~
Main.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
      |                                ^
Main.cpp:50:2: note: in expansion of macro 'rep'
   50 |  rep(i,y){
      |  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21584 KB Output is correct
2 Correct 10 ms 21416 KB Output is correct
3 Correct 10 ms 21452 KB Output is correct
4 Correct 10 ms 21452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21452 KB Output is correct
2 Correct 10 ms 21452 KB Output is correct
3 Correct 10 ms 21412 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21452 KB Output is correct
2 Correct 10 ms 21432 KB Output is correct
3 Correct 10 ms 21400 KB Output is correct
4 Correct 10 ms 21324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21580 KB Output is correct
2 Correct 15 ms 21580 KB Output is correct
3 Correct 17 ms 21660 KB Output is correct
4 Correct 16 ms 21660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21656 KB Output is correct
2 Correct 14 ms 21584 KB Output is correct
3 Correct 13 ms 21608 KB Output is correct
4 Correct 14 ms 21580 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21580 KB Output is correct
2 Correct 14 ms 21572 KB Output is correct
3 Correct 14 ms 21584 KB Output is correct
4 Correct 14 ms 21596 KB Output is correct