oj.uz

Submission #199374

# Submission time Handle Problem Language Result Execution time Memory
199374 2020-01-31T19:34:48 Z CaroLinda Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 274 ms 55596 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 0 ;
    if( c == 'C' ) return 1 ;
    if( c == 'G' ) return 2 ;
    return 3 ;
}

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 )
            {
                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 < 4 ; 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(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:107: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:111:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%s", str ) ;
      ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 32504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 55596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 38772 KB Output is correct
2 Incorrect 85 ms 36732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 32504 KB Output isn't correct
2 Halted 0 ms 0 KB -