oj.uz

Submission #489282

# Submission time Handle Problem Language Result Execution time Memory
489282 2021-11-21T22:07:05 Z inksamurai Vlak (COCI20_vlak) C++17
70 / 70
 74 ms 71652 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=2e5+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 47 ms 70680 KB Output is correct
2 Correct 46 ms 70712 KB Output is correct
3 Correct 46 ms 70736 KB Output is correct
4 Correct 48 ms 70736 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 70760 KB Output is correct
2 Correct 47 ms 70736 KB Output is correct
3 Correct 52 ms 70732 KB Output is correct
4 Correct 48 ms 70752 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 70704 KB Output is correct
2 Correct 53 ms 70664 KB Output is correct
3 Correct 50 ms 70684 KB Output is correct
4 Correct 48 ms 70680 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70748 KB Output is correct
2 Correct 57 ms 70720 KB Output is correct
3 Correct 64 ms 70700 KB Output is correct
4 Correct 61 ms 70700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 71392 KB Output is correct
2 Correct 53 ms 71652 KB Output is correct
3 Correct 53 ms 71532 KB Output is correct
4 Correct 53 ms 71644 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 70984 KB Output is correct
2 Correct 52 ms 71264 KB Output is correct
3 Correct 53 ms 71236 KB Output is correct
4 Correct 51 ms 71208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 71152 KB Output is correct
2 Correct 74 ms 71404 KB Output is correct
3 Correct 72 ms 71464 KB Output is correct
4 Correct 60 ms 71440 KB Output is correct