Submission #199377

# Submission time Handle Problem Language Result Execution time Memory
199377 2020-01-31T20:05:19 Z CaroLinda Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
1500 ms 101368 KB
#include <bits/stdc++.h>

#define ff first
#define ss second

const int MOD = 1e9+7 ;
const int MAX = 1e5+10 ;
const int SMAX = 2e6+10 ;
const int base = 31 ;

using namespace std ;

int resp[MAX] ;

int get_val(char c) 
{
    if( c == 'A' ) return 1 ;
    if( c == 'C' ) return 2 ;
    if( c == 'G' ) return 3 ;
    return 4 ;
}

struct Trie
{
   
    struct Node
    {
        int v[5] , soma ;
        vector<int> end_here ;
        Node() { for(int i = 0 ; i < 5 ; i++ ) v[i] = soma =0 ; }
    } ;
   
    int ptr ;
    vector<Node> adj ;
    
    Trie() { adj.push_back( Node() ) ; }
    
    void add( vector<char> v, int idx, int para_somar )
    {
        
        int curr = 0 ;
        
        for(int i = 0 ; i < (int)(v.size()) ; i++ )
        {
            int val = get_val( v[i] ) ;
            adj[curr].soma += para_somar ;
            
            if( adj[curr].v[val] == 0 )
            {
                if( para_somar == 1 ) return ;
                adj.push_back( Node() ) ;
                adj[curr].v[val] = ++ptr ;
            }
            
            curr = adj[curr].v[val] ;
            
        }
        
        if( para_somar == 0 )
            adj[curr].end_here.push_back(idx) ;
            
        adj[curr].soma += para_somar; 
        
        
    }
    
    void anda()
    {
        
        queue<int> fila ;
        fila.push(0) ;
        
        while(!fila.empty())
        {
            int curr = fila.front() ;
            fila.pop() ;
                
            
            for(int i : adj[curr].end_here )
                resp[i] = adj[curr].soma ;
            
            for(int i = 0 ; i < 5 ; i ++ )
                if( adj[curr].v[i] > 0 )
                    fila.push( adj[curr].v[i] ) ;
            
        }
        
    }
    
    
} ;

int n , m ;
vector<int> dif_tams ;
bool marc_tams[SMAX] ;
char str[MAX] ;
vector<char> to_sell[MAX] , to_buy_pref[MAX] , to_buy_suf[MAX] ;
vector< pair< long long int , int > > aux ;
long long pot[SMAX] ;
vector<long long> my_hash ;
unordered_map<long long , int> mp ;
Trie our_trie[MAX] ;
string s ;

int main()
{
	//Reading input
	scanf("%d%d", &n , &m) ;
	
	for(int i = 1 ; i <= n ; i++ )
	{
	    scanf("%s", str ) ;
	   
	   int _n = strlen(str) ;
	   
	   for(int j = 0 ; j < _n ; j++ ) to_sell[i].push_back( str[j] ) ;
	    
	}
	getchar() ;
	
	for(int i = 1 ; i <= m ; i++ )
	{
	    getline( cin , s ) ;
	    int _n = s.size() , j = 0;
	    
	   for(; s[j] != ' ' ; j++ )
	    to_buy_pref[i].push_back( s[j] ) ;
	   j ++ ;
	   
	   for(; j < _n ; j++ ) to_buy_suf[i].push_back( s[j] ) ;
	    
	}
    //
    
	

	pot[0] = 1 ;
	for(int i = 1 ; i < SMAX ; i++ ) pot[i] = ( pot[i-1] * base ) % MOD ;
	
	for(int i = 1 ; i <= m ; i++ )
	{
	    
	    marc_tams[ to_buy_suf[i].size() ] = true ;
	    
	   long long cur_sum = 0LL ;
	    
	  for(int j = to_buy_suf[i].size() - 1, idx = 0 ; j >= 0 ; j-- , idx++ )
	   {
	       cur_sum = ( cur_sum * base ) % MOD ;
	       cur_sum = ( cur_sum + get_val( to_buy_suf[i][j] ) ) % MOD ;
	   } 

	  
	   
	   my_hash.push_back( cur_sum ) ;
	   mp.insert( make_pair(cur_sum,0) ) ; 
	   
	}



    int Key = 1 ;
    for(auto &p : mp ) p.ss = Key ++ ;
	
	
	for(int i = 1 ; i <= m ; i++ )
    {
        my_hash[i-1] = mp[ my_hash[i-1] ] ;
        our_trie[ my_hash[i-1] ].add( to_buy_pref[i] , i , 0 ) ;
    }
    
    for(int i = 1 ; i <= SMAX ; i++ )
        if( marc_tams[i] ) dif_tams.push_back(i) ;
        
  // for(auto &p : mp ) printf("%lld %d\n" , p.ff, p.ss ) ;
    
    for(int i = 1 ; i <= n ; i++ )
    {
        
        long long cur_sum = 0LL ;
        
        for(int j = to_sell[i].size() - 1 , tot = 1 , idx = 0 ; j >= 0 ; j -- , tot++ )
        {
            cur_sum = ( cur_sum * base ) % MOD ;
            cur_sum = ( cur_sum + get_val( to_sell[i][j] ) ) % MOD ;
            
            if( tot == dif_tams[idx] ) 
            {
                idx ++ ;
                
                unordered_map<long long, int>::iterator it = mp.find(cur_sum) ;
                
                if( it == mp.end() ) continue ;
                
                our_trie[ it->ss ].add( to_sell[i] , -1 , 1 ) ;
                
            }
            
        }
        
    }
    
    for(int i = 1 ; i < Key ; i++ ) our_trie[i].anda() ;
    
    for(int i = 1 ; i <= m ; i++ ) printf("%d\n" , resp[i] ) ;
	
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n , &m) ;
  ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:112:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%s", str ) ;
      ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 45 ms 32504 KB Output is correct
2 Correct 43 ms 32504 KB Output is correct
3 Correct 43 ms 32504 KB Output is correct
4 Correct 42 ms 32504 KB Output is correct
5 Correct 42 ms 32504 KB Output is correct
6 Correct 42 ms 32376 KB Output is correct
7 Correct 44 ms 32504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 262 ms 48636 KB Output is correct
2 Correct 265 ms 43128 KB Output is correct
3 Correct 463 ms 39160 KB Output is correct
4 Correct 464 ms 43128 KB Output is correct
5 Correct 264 ms 78680 KB Output is correct
6 Correct 255 ms 78200 KB Output is correct
7 Execution timed out 1508 ms 101368 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 95 ms 38392 KB Output is correct
2 Correct 83 ms 36092 KB Output is correct
3 Correct 94 ms 37108 KB Output is correct
4 Correct 88 ms 36336 KB Output is correct
5 Correct 86 ms 35932 KB Output is correct
6 Correct 93 ms 37236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 45 ms 32504 KB Output is correct
2 Correct 43 ms 32504 KB Output is correct
3 Correct 43 ms 32504 KB Output is correct
4 Correct 42 ms 32504 KB Output is correct
5 Correct 42 ms 32504 KB Output is correct
6 Correct 42 ms 32376 KB Output is correct
7 Correct 44 ms 32504 KB Output is correct
8 Correct 262 ms 48636 KB Output is correct
9 Correct 265 ms 43128 KB Output is correct
10 Correct 463 ms 39160 KB Output is correct
11 Correct 464 ms 43128 KB Output is correct
12 Correct 264 ms 78680 KB Output is correct
13 Correct 255 ms 78200 KB Output is correct
14 Execution timed out 1508 ms 101368 KB Time limit exceeded
15 Halted 0 ms 0 KB -