oj.uz

Submission #489281

# Submission time Handle Problem Language Result Execution time Memory
489281 2021-11-21T22:06:47 Z inksamurai Vlak (COCI20_vlak) C++17
40 / 70
 9 ms 8140 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HIYw7x ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

const int _n=2e4+1;

struct trie{
	vec(vi) to;
	int cnt=0;
	void init(int n){
		to=vec(vi)(n,vi(27,-1));
		cnt=0;
	}
};

int main(){
_3HIYw7x;
	int n;
	cin>>n;
	vec(string) a(n);
	rep(i,n){
		cin>>a[i];
	}
	int m;
	cin>>m;
	vec(string) b(m);
	rep(i,m){
		cin>>b[i];
	}
	trie _a;
	_a.init(_n);
	rep(i,n){
		int root=0;
		rep(j,sz(a[i])){
			int x=a[i][j]-'a';
			if(_a.to[root][x]==-1){
				_a.cnt++;
				_a.to[root][x]=_a.cnt;
			}
			root=_a.to[root][x];
		}
	}
	trie _b;
	_b.init(_n);
	rep(i,m){
		int root=0;
		rep(j,sz(b[i])){
			int x=b[i][j]-'a';
			if(_b.to[root][x]==-1){
				_b.cnt++;
				_b.to[root][x]=_b.cnt;
			}
			root=_b.to[root][x];
		}		
	}
	vec(vi) dp(_n,vi(2,-1));
	auto dfs=[&](auto self,int v,int v1,int t)->int{
		if(dp[v][t]!=-1) return dp[v][t];
		int pok=0;
		rep(ch,26){
			if(t==0){
				if(_a.to[v][ch]!=-1){
					if(_b.to[v1][ch]==-1){
						pok=1;
						break;
					}
					pok=pok or !self(self,_a.to[v][ch],_b.to[v1][ch],1);
				}
			}else{
				if(_b.to[v1][ch]!=-1){
					if(_a.to[v][ch]==-1){
						pok=1;
						break;
					}
					pok=pok or !self(self,_a.to[v][ch],_b.to[v1][ch],0);
				}
			}
		}
		return dp[v][t]=pok;
	};
	dfs(dfs,0,0,0);
	cout<<(dp[0][0]?"Nina":"Emilija")<<"\n";
//	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7284 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 8140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 7372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -