oj.uz

Submission #474095

# Submission time Handle Problem Language Result Execution time Memory
474095 2021-09-16T21:33:19 Z CaroLinda Vlak (COCI20_vlak) C++14
70 / 70
 46 ms 15976 KB 
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
 
const int MAXN = 2e5+10 ;
 
using namespace std ;

int tam ;
int rt[2] ;
vector<int> rev, depth , dp ;
vector< vector<int> > node ;
char str[MAXN] ;

int createNode()
{
	node.push_back( vector<int>( 26, -1 ) )	;
	rev.push_back(-1) ;
	depth.push_back(0) ;
	dp.push_back(0) ;
	return sz(node)-1 ;
}

void add_string(int curNode, int idx)
{
	if( idx == tam ) return ;
	
	int viz = str[idx]-'a' ;
	
	if( node[curNode][viz] == -1 )
	{
		int aux = createNode() ;
		depth[aux] = depth[curNode] + 1 ;
		node[curNode][viz] = aux ;
	}
	
	add_string( node[curNode][viz] , idx+1 ) ;
	
}

void dfs(int x, int y)
{
	rev[x] = y ;
	rev[y] = x ;
	
	for(int i = 0 ; i < 26 ; i++ )
	{
		if(node[x][i] == -1 || node[y][i] == -1 ) continue ;
		dfs(node[x][i] , node[y][i]) ;
	}
}

int main()
{
	for(int i = 0 ; i < 2 ; i++ )
	{
		rt[i] = createNode() ;	
		
		int x ;
		scanf("%d", &x ) ;
		for(int j = 0  ; j< x ; j++ )
		{
			scanf("%s", str ) ;
		
			tam = strlen(str) ;
			
			add_string( rt[i] , 0 ) ;
		}
	}	
	
	dfs(rt[0], rt[1] ) ;
	
	vector<int> vec ;
	for(int i = 0 ; i < sz(node) ; i++ ) vec.pb(i) ;
	sort(all(vec),[&](int x, int y) { return depth[x] > depth[y] ; }) ;
	
	for(auto e : vec )
	{
		int cur = 0 ;
		for(int i = 0 ; i < 26 ; i++ )
		{
			if(node[e][i] == -1 ) continue ;
			if( rev[node[e][i]] == -1 || dp[ rev[node[e][i]] ] == 0 ) cur = 1 ;
		}
		dp[e] = cur ;
	}
	
	printf("%s\n", dp[0] == 1 ? "Nina" : "Emilija" ) ;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d", &x ) ;
      |   ~~~~~^~~~~~~~~~~
Main.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    scanf("%s", str ) ;
      |    ~~~~~^~~~~~~~~~~~

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 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 #4
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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14916 KB Output is correct
2 Correct 40 ms 14076 KB Output is correct
3 Correct 39 ms 13612 KB Output is correct
4 Correct 41 ms 14820 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15244 KB Output is correct
2 Correct 42 ms 15976 KB Output is correct
3 Correct 46 ms 14632 KB Output is correct
4 Correct 39 ms 14836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14364 KB Output is correct
2 Correct 41 ms 14136 KB Output is correct
3 Correct 39 ms 14432 KB Output is correct
4 Correct 44 ms 15356 KB Output is correct