답안 #229536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229536	2020-05-04T23:36:35 Z	Uzumaki_Naturoo	Rima (COCI17_rima)	C++14	0 / 140	1000 ms	48632 KB

rima

/// You just can't beat the person who never gives up
/// ICPC next year

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5+5 ;

int n ;
string str ;

const int base = 29 ;
int mod[2] = {(int)1e9+9 ,(int)1e9+7};
int p[N][2] = {{1, 1}} ;
int inv[N][2] = {{1, 1}} ;
int pwr(int b,int md){
    int p = md - 2 ;
    int res = 1 ;
    while(p){
        if(p&1) res = (1ll * res * b) %md;
        b = (1ll * b * b) %md;
        p >>= 1;
    }
    return res ;
}
void init(){
    for(int i=1;i<N;++i)
        for(int j=0;j<2;++j){
            p[i][j] = (1ll * p[i-1][j] * base) %mod[j] ;
            inv[i][j] = pwr(p[i][j], mod[j]) ;
        }
}

pair<int,int> push_back(pair<int,int> cur,int x){
    int val[2] = {cur.first,cur.second};
    for(int i=0;i<2;++i){
        val[i] = (1ll * val[i] * base) %mod[i];
        val[i] = (val[i] + x) %mod[i];
    }
    return make_pair(val[0],val[1]) ;
}
pair<int,int> pop_back(pair<int,int> cur){
    int val[2] = {cur.first,cur.second};
    for(int i=0;i<2;++i){
        int v = val[i] %base ;
        val[i] = ((val[i] - v) %mod[i] + mod[i]) %mod[i] ;
        val[i] = (1ll * val[i] * inv[1][i]) %mod[i];
    }
    return make_pair(val[0],val[1]) ;
}
pair<int,int> hash_val[N] ;
int main(){
    init() ;
    cin >> n ;
    map<pair<int,int>,int> cnt ,cnt2 ;
    for(int i=0;i<n;++i){
        cin >> str ;
        reverse(str.begin(),str.end());
        pair<int,int> cur = {0,0} ;
        for(int i=0;i<str.size();++i){
            cur = push_back(cur,str[i]-'a'+1);
        }
        hash_val[i] = cur ;
        ++cnt[cur] ;
        ++cnt2[pop_back(cur)];
    }
    int ans = 0 ;
    for(int i=0;i<n;++i){
        int cur = 0 ;
        pair<int,int> h = hash_val[i] ;
        while(h!=make_pair(0,0)){
            if(!cnt.count(h)) break ;
            h = pop_back(h);
            cur += cnt2[h] ;
        }
        ans = max(ans ,cur);
    }
    printf("%d",ans);
    return 0;
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<str.size();++i){
                     ~^~~~~~~~~~~

Subtask #1

0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	489 ms	8312 KB	Output isn't correct
2	Incorrect	490 ms	8184 KB	Output isn't correct
3	Incorrect	491 ms	8312 KB	Output isn't correct
4	Execution timed out	1097 ms	48632 KB	Time limit exceeded
5	Incorrect	695 ms	11416 KB	Output isn't correct
6	Incorrect	538 ms	9488 KB	Output isn't correct
7	Incorrect	532 ms	9224 KB	Output isn't correct
8	Incorrect	524 ms	9204 KB	Output isn't correct
9	Incorrect	723 ms	13080 KB	Output isn't correct
10	Incorrect	527 ms	9356 KB	Output isn't correct