Submission #200220

#	Time	Username	Problem	Language	Result	Execution time	Memory
200220		CaroLinda	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1525 ms	90616 KiB

selling_rna

#include <bits/stdc++.h>
     
    #define ff first
    #define ss second
     
    const int MOD = 1e8 ;
    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 marc[MOD+10] ;
     
    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] ) ;
    	    
    	}
        //
        
    	
     
    	mp.reserve(m) ;
    	
    	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 ) ;
    	   marc[cur_sum] = 1 ;
    	   
    	}
     
     
     
        int Key = 1 ;
        for(int i = 0 ; i < MOD  ; i++ ) 
            if(marc[i]) marc[i] = Key ++ ;
    	
    	
    	for(int i = 1 ; i <= m ; i++ )
        {
            my_hash[i-1] = marc[ 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 ++ ;
                    
                    if( marc[cur_sum] == 0 ) continue ;
                    
                    our_trie[ marc[cur_sum] ].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 (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:109:11: 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:113:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%s", str ) ;
          ~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40