oj.uz

답안 #229547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229547 2020-05-05T03:46:47 Z Uzumaki_Naturoo Rima (COCI17_rima) C++14
56 / 140
 1000 ms 127352 KB 
/// 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[4] = {(int)1e9+9 ,(int)1e9+7 ,(int)1e9-63 ,(int)1e9-71};
struct rabinKarp{
    int val[4] ;
    rabinKarp(){
        memset(val,0,sizeof val);
    }
    void push_back(int x){
        for(int i=0;i<4;++i){
            val[i] = (1ll * val[i] * base) %mod[i];
            val[i] = (val[i] + x) %mod[i];
        }
    }
    pair<ull ,ull> hashVal(){
        ull a = val[0] ,b = val[2] ;
        a *= 1e10 ,b *= 1e10 ;
        a += val[1] ,b += val[3] ;
        return {a ,b} ;
    }
};
int n ;
char str[M] ;
vector<pair<ull,ull>> h[N] ;
map<pair<ull,ull> ,int> cnt ;
set<pair<ull,ull>> all ;

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(make_pair(0,0));
        for(int j=0;j<m;++j){
            rbk.push_back(str[j]-'a'+1);
            h[i].push_back(rbk.hashVal());
        }
        ++cnt[h[i][h[i].size()-2]] ;
        all.insert(h[i].back());
    }
    int ans = 0 ;
    for(int i=0;i<n;++i){
        int cur = 0 ;
        while(h[i].size()>=2 && all.count(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 'int main()':
rima.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
rima.cpp:41: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 12032 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Execution timed out 1060 ms 127352 KB Time limit exceeded
5 Correct 317 ms 66300 KB Output is correct
6 Incorrect 67 ms 25176 KB Output isn't correct
7 Incorrect 54 ms 21736 KB Output isn't correct
8 Incorrect 46 ms 21732 KB Output isn't correct
9 Incorrect 268 ms 77528 KB Output isn't correct
10 Incorrect 45 ms 23148 KB Output isn't correct