답안 #229621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229621	2020-05-05T12:39:22 Z	Uzumaki_Naturoo	Rima (COCI17_rima)	C++14	140 / 140	484 ms	172464 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 = 3e6+5 ;

int n ,m ,sz ;
vector<pair<int,int>> to[N] ;
char str[N] ;
bool en[N] ;
void insert_str(){
    int cur = 0 ;
    for(int i=0;i<m;++i){
        int cc = str[i] - 'a' ;
        int j = 0 ;
        while(j<to[cur].size() && to[cur][j].first!=cc) ++j ;
        if(j==to[cur].size()) to[cur].push_back({cc ,++sz}) ;
        cur = to[cur][j].second ;
    }
    en[cur] = 1 ;
}
int mem[N][2][2] ;
int dfs(int cur,bool is,bool ok){
    int&ret = mem[cur][is][ok];
    if(~ret) return ret;
    ret = 0 ;
    int here = 0 ;
    for(auto i:to[cur]) here += en[i.second] ;
    if(!is){
        for(auto i:to[cur]){
            ret = max(ret ,dfs(i.second,0,0));
            if(en[i.second]) ret = max(ret ,1+dfs(i.second,1,0));
        }
        vector<int> v ;
        for(auto i:to[cur]) if(en[i.second]){
            v.push_back(dfs(i.second,1,1));
            sort(v.rbegin(),v.rend());
            if(v.size()>2) v.pop_back();
        }
        int s = 0 ;
        for(int i:v) s += i ;
        return ret = max(ret ,here + s) ; ;
    }
    if(is && !ok){
        vector<int> v ;
        for(auto i:to[cur]) if(en[i.second]){
            v.push_back(dfs(i.second,1,1));
            sort(v.rbegin(),v.rend());
            if(v.size()>2) v.pop_back();
        }
        int s = 0 ;
        for(int i:v) s += i ;
        ret = max(ret ,here + s);
        return ret ;
    }
    if(!here) return ret ;

    ret = max(ret,here) ;
    for(auto i:to[cur]) if(en[i.second]) ret = max(ret ,here + dfs(i.second,1,1)) ;
    return ret ;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s",str);
        m = strlen(str) ;
        reverse(str,str+m);
        insert_str();
    }
    memset(mem,-1,sizeof mem);
    printf("%d",dfs(0,0,0));
    return 0;
}

Compilation message

rima.cpp: In function 'void insert_str()':
rima.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j<to[cur].size() && to[cur][j].first!=cc) ++j ;
               ~^~~~~~~~~~~~~~~
rima.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(j==to[cur].size()) to[cur].push_back({cc ,++sz}) ;
            ~^~~~~~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
rima.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",str);
         ~~~~~^~~~~~~~~~

Subtask #1

140.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	71 ms	117752 KB	Output is correct
2	Correct	69 ms	117752 KB	Output is correct
3	Correct	67 ms	117624 KB	Output is correct
4	Correct	484 ms	132472 KB	Output is correct
5	Correct	96 ms	120312 KB	Output is correct
6	Correct	116 ms	170360 KB	Output is correct
7	Correct	118 ms	170300 KB	Output is correct
8	Correct	124 ms	170104 KB	Output is correct
9	Correct	150 ms	172464 KB	Output is correct
10	Correct	121 ms	170264 KB	Output is correct