답안 #229549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229549	2020-05-05T04:00:33 Z	Uzumaki_Naturoo	Rima (COCI17_rima)	C++14	56 / 140	1000 ms	89160 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 ,M = 3e6+5 ;

typedef unsigned long long ull ;
const int base = 29 ;
int mod[2] = {(int)1e9+9 ,(int)1e9+7};
struct rabinKarp{
    int val[2] ;
    rabinKarp(){
        memset(val,0,sizeof val);
    }
    void push_back(int x){
        for(int i=0;i<2;++i){
            val[i] = (1ll * val[i] * base) %mod[i];
            val[i] = (val[i] + x) %mod[i];
        }
    }
    ull hashVal(){
        return (ull)val[0] * 1e10 + val[1] ;
    }
};
int n ;
char str[M] ;
vector<ull> h[N] ;
int cnt[M] ;
bool is[M] ;

void compress(){
    map<ull,int> mp ;
    for(int i=0;i<n;++i) for(auto go:h[i]) mp[go] ;
    int v = 0 ;
    for(auto&go:mp) go.second = v++ ;
    for(int i=0;i<n;++i) for(int j=0;j<h[i].size();++j) h[i][j] = mp[h[i][j]] ;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s",str);
        int m = strlen(str);
        reverse(str,str+m) ;
        rabinKarp rbk ;
        h[i].push_back(0);
        for(int j=0;j<m;++j){
            rbk.push_back(str[j]-'a'+1);
            h[i].push_back(rbk.hashVal());
        }
    }
    compress() ;
    for(int i=0;i<n;++i){
        ++cnt[h[i][h[i].size()-2]] ;
        is[h[i].back()] = 1 ;
    }
    int ans = 0 ;
    for(int i=0;i<n;++i){
        int cur = 0 ;
        while(h[i].size()>=2 && is[h[i].back()]){
            cur += cnt[h[i][h[i].size()-2]] ;
            h[i].pop_back();
        }
        ans = max(ans ,cur);
    }
    printf("%d",ans);
    return 0;
}

Compilation message

rima.cpp: In function 'void compress()':
rima.cpp:40:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<n;++i) for(int j=0;j<h[i].size();++j) h[i][j] = mp[h[i][j]] ;
                                      ~^~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
rima.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",str);
         ~~~~~^~~~~~~~~~

Subtask #1

56.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	12160 KB	Output is correct
2	Correct	12 ms	12160 KB	Output is correct
3	Correct	12 ms	12160 KB	Output is correct
4	Execution timed out	1100 ms	89160 KB	Time limit exceeded
5	Correct	543 ms	41208 KB	Output is correct
6	Incorrect	614 ms	38472 KB	Output isn't correct
7	Incorrect	522 ms	36704 KB	Output isn't correct
8	Incorrect	518 ms	36316 KB	Output isn't correct
9	Execution timed out	1049 ms	66028 KB	Time limit exceeded
10	Incorrect	487 ms	36088 KB	Output isn't correct